题目描述

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

样例

示例 1:

输入: [1,2,0]
输出: 3
示例 2:

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

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

算法1

(数组 + 利用下标) $O(n)$

把1~n的数放到数组下标0~n-1的位置；
再遍历数组，如果下标为i，元素不是i + 1，说明缺了这个数。

时间复杂度

swap元素到相应位置过程中，每个元素最多被换$O(1)$次，总时间复杂度$O(n)$；
遍历数组，$O(n)$;
合起来还是$O(n)$.

参考文献

C++ 代码

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();

        for (int i = 0; i < n; ++i){
            while (nums[i] <= n && nums[i] >= 1 && nums[nums[i] - 1] != nums[i]){
                swap(nums[i], nums[nums[i] - 1]);
            }
        }

        for (int i = 0; i < n; ++i){
            if (nums[i] != i + 1) return i + 1;
        }

        return n + 1;
    }
};