First Missing Positive

解题思路

  1. 先思考最粗暴的解法：自然是新建一个同等大小的数组，然后遍历输入，将每个输入的正整数放到对应的位置，然后遍历这个新建的数组就知道缺失的第一个正数是哪个了。

  2. 于是，为了达到常数级别空间，就不能新建数组，那么久考虑在原有数组上动手脚。

代码


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