標(biāo)簽：數(shù)組，難

問題描述

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

給定未排序整型數(shù)組，查找缺失的最小正整數(shù)。
示例:
輸入: [1,2,0]
輸出: 3

輸入: [3,4,-1,1]
輸出: 2

輸出: [7,8,9,11,12]
輸出: 1

注意:
算法運(yùn)行時(shí)間 在O(n)內(nèi)，且使用空間復(fù)雜度為常量。

解決方案

比較直觀的想法是先對(duì)數(shù)組進(jìn)行排序，然后遍歷數(shù)組查找缺失的最小正整數(shù)。但是本題要求運(yùn)行時(shí)間在O(n)內(nèi)，常見排序算法的時(shí)間復(fù)雜度無法滿足。

方法一：

使用位圖存儲(chǔ)每個(gè)出現(xiàn)的正整數(shù)，然后遍歷正整數(shù)尋找未出現(xiàn)過的整數(shù)。

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        unsigned char *bitmap = new unsigned char[1<<28]; 
        int result;
        for(int i = 0; i < nums.size(); i++) {
            if(nums[i] <= 0)
                continue;
            int idx = nums[i] / 8;
            int bit = nums[i] % 8;
            bitmap[idx] = bitmap[idx] | 1 << bit;
        }
        for(int i = 1; i <= INT_MAX; i++) {
            int idx = i / 8;
            int bit = i % 8;
            if((bitmap[idx] & (1 << bit)) == 0)
                return i;
        }
        return result;
    }
};

算法分析：

• 時(shí)間復(fù)雜度：Θ(n)
• 空間復(fù)雜度：O(1)。本題中額外存儲(chǔ)空間量為2²⁸字節(jié)。
• 運(yùn)行時(shí)間：4ms

方法二：

核心思想是把A[i]放到位置A[i] - 1處。這需要兩次遍歷數(shù)組。

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int len = nums.size();
        if(len == 0)
            return 1;
        int i = 0;
        while(i < len) {
            if(nums[i] <= 0 || nums[i] > len)
                i++;
            else if(nums[nums[i] - 1] == nums[i]) {
                i++;
            } else {
                int temp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = temp;
            }
        }
        for(i = 0; i < len; i++) {
            if(nums[i] != i + 1)
                return i+1;
        }
        return i + 1;
    }
};

算法分析：

• 時(shí)間復(fù)雜度：Θ(n)
• 空間復(fù)雜度：O(1)。
• 運(yùn)行時(shí)間：4ms