缺失的第一个正数

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

示例 1:

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

示例 2:

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

示例 3:

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

说明:

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

/*
思路：
(1) 如果想要找到缺失的最小正数，那么正常情况nums.size = n, 我们需要关心的数据是[1, 2, ,3, ... , n];
(2) 小于等于0的数字我们不需要关心，大于n的数字我们也不需要管（因为正常情况以1递增该数组是不可能超过n的）
(3) 所以我们关心的数据都是1 <= x <= n的；所有的数据必须以1来递增，否则就会存在缺失；
(4) 我们可以将数组的下标当作hash map的key值，将所有为x的有效数字放入下标为x-1的数组中，无效数字我们暂时不关心，
可以利用一次遍历完成此操作；
(5) 接着我们再利用一次遍历去找到第一个无法对应下标的数字，证明该下标存放是无效数字，因此在该位置上存在缺失，为修小缺失数；
*/

class Solution {
public:
    void swap(int &x, int &y) {
        int temp = y;
        y = x;
        x = temp;
    }
    int firstMissingPositive(vector<int>& nums) {
        for(int i = 0; i < nums.size();) {
            if(nums[i] <= 0 || nums[i] == (i + 1)) {
                ++i;
                continue;
            }
            if(nums[i] >= 1 && nums[i] <= nums.size()) {
                if(nums[i] != nums[nums[i] - 1])
                    swap(nums[i], nums[nums[i] - 1]);
                else ++i; // [1,1]
            } else ++i;
        }
        
        int cur = 1;
        for(int i = 0; i < nums.size(); ++i) {
            if(nums[i] != i + 1) return cur;
            else ++cur;
        }
        return cur; // [1]
    } 
};