標(biāo)簽： C++ 算法 LeetCode 數(shù)組

每日算法——leetcode系列

問(wèn)題 First Missing Positive

Difficulty: Hard

Given an unsorted integer array, find the first missing positive integer.

For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

Your algorithm should run in O(n) time and uses constant space.

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        
    }
};

翻譯

第一個(gè)缺失的正整數(shù)

難度系數(shù)：困難

給定一個(gè)無(wú)序數(shù)組，找出第一個(gè)缺失的正整數(shù)。
例如：
給定[1,2,0] 返回 3,
[3,4,-1,1] 返回 2。
算法的時(shí)間復(fù)雜度為O(n), 空間復(fù)雜度為常數(shù)。

思路

此題一看想排序，如果有序后，找第一個(gè)缺失的正整數(shù)，那就從1開(kāi)始查，如果數(shù)組中查到有1，那就查2，如此查到最后看待查的數(shù)就是要的結(jié)果，要查的數(shù)可以用索引來(lái)表示。
排序算法時(shí)間復(fù)雜度為O(n)的是桶排序，這里關(guān)鍵是要找到桶的個(gè)數(shù)，由于只查正整數(shù)，假定數(shù)組的長(zhǎng)序?yàn)閚，那n-1個(gè)桶放正整數(shù)就夠了，遍歷數(shù)組，小于1和大于n-1的數(shù)都不用管，這樣就可以把數(shù)組中1到n-1的數(shù)剔出放在相應(yīng)位置的桶中，再查缺失元素，但這種方案空間復(fù)雜度為O(n)，不為常數(shù)。
下面分析排序：
假定： 桶k裝的數(shù)為m

• k == m 不變
• k != m 則數(shù)m應(yīng)該裝到第m個(gè)桶，則把桶m的數(shù)和桶k的數(shù)交換，直接交換過(guò)來(lái)的數(shù)為m就不用交換
  這里可能會(huì)給人感覺(jué)時(shí)間復(fù)雜度不為O(n)了，由于每一次交換后都會(huì)把一個(gè)數(shù)放到正確的桶上，所以平均下來(lái)最后還是O（n）

代碼

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        
        // sort
        int n = static_cast<int>(nums.size());
        int num;
        for(int i = 0; i < n; ++i) {
            num = nums[i];
            while (num > 0 && num < n && nums[num-1] != num) {
                swap(nums[i], nums[num-1]);
                num = nums[i];
            }
        }
        
        // find
        int wantToFind = 1;
        for (auto &item : nums){
            if (item == wantToFind){
                ++wantToFind;
            }
        }
        return wantToFind;
    }
};

嘮叨
教初中娃兒編程真是一個(gè)難事，能力不足，想要培養(yǎng)一個(gè)孩子的編程興趣還完全做不到