标签：数组，难

问题描述

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

给定未排序整型数组，查找缺失的最小正整数。
示例:
输入: [1,2,0]
输出: 3

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

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

注意:
算法运行时间 在O(n)内，且使用空间复杂度为常量。

解决方案

比较直观的想法是先对数组进行排序，然后遍历数组查找缺失的最小正整数。但是本题要求运行时间在O(n)内，常见排序算法的时间复杂度无法满足。

方法一：

使用位图存储每个出现的正整数，然后遍历正整数寻找未出现过的整数。

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;
    }
};

算法分析：

• 时间复杂度：Θ(n)
• 空间复杂度：O(1)。本题中额外存储空间量为2²⁸字节。
• 运行时间：4ms

方法二：

核心思想是把A[i]放到位置A[i] - 1处。这需要两次遍历数组。

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;
    }
};

算法分析：

• 时间复杂度：Θ(n)
• 空间复杂度：O(1)。
• 运行时间：4ms