题目描述

给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。

提示：你的算法的时间复杂度应为O(n)，并且只能使用常数级别的额外空间。

前言

若不考虑时空复杂度，可以使用辅助空间记录出现的数字的方式实现，亦或者从1开始暴力比较每一个数组元素来实现。而按照题目中的要求，则需要尝试利用题目所给出的数组空间来协助完成。

思路与算法

方法一：哈希表

考虑n个元素的整数数组，未出现的最小的正整数只可能在[1, n+1]。若n个元素存放了[1,n]的所有整数，则最小未出现的正数未n+1；否则，最小未出现的正数一定在[1, n]之间。我们使用负数来标记当前元素对应的下标的值存在。

首先，先将原始数组中的负数全部变为n+1，因为若出现负数，则最小未出现正数一定不是n+1。全部变成正数后，就不会影响后面的标记操作。在遍历时，每次取当前元素的绝对值（这样我们既可以进行取负值标记，同时也保证了不破坏当前元素的原始值），若绝对值x在[1, n]之间，则将下标为x-1的元素值取反，表示x出现过。再进行一遍遍历，若当前下标i的元素值不为i+1则返回i+1；若均等于，则返回n+1。

代码：

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for(int& num : nums){
            if(num <= 0){
                num = n+1;
            }
        }
        for(int i = 0; i < n; i++){
            int num = abs(nums[i]);
            if(num <= n){
                nums[num-1] = -abs(nums[num-1]);
            }
        }
        for(int i = 0; i < n; i++){
            if(nums[i] > 0) return i+1;
        }
        return n+1;
    }
};

复杂度分析：

• 时间复杂度：O(n)，n为数组的长度。
• 空间复杂度： O(1)。

方法二：置换

除了打标记，我们可以尝试将值为x的元素归位下标x-1。举个例子[3, 4, -1, 1]，归位后的数组应为[1, -1, 3, 4]，如此，我们就可以知道缺少的位置。

对于x = nums[i]，若x∈[1, n]，则交换nums[i]和nums[x-1]的值。但是注意，若nums[i] = x = nums[x-1]则会陷入死循环，此时说明x已经位于正确的位置了，所以可以跳出循环，开始遍历下一个数。

代码

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

复杂度分析：

• 时间复杂度：O(n)，n为数组的长度。
• 空间复杂度： O(1)。