41. First Missing Positive

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int sz = nums.size();
        for(int i = 0; i < sz; ++i)
        {
            while(nums[i] > 0 && nums[i] <= sz && nums[i] != nums[nums[i] - 1]) // 这里之所以使用nums[i] != nums[nums[i] - 1]而不是nums[i] != i + 1, 是为了防止2个相同的数出现在这两处。这里是让当前的数字搬到正确的地方去，而不是让当前地方具有正确的数字。因为如果当前地方的数字缺失，那么永远也出不了循环。
                swap(nums[i], nums[nums[i] - 1]);
        }
        for(int i = 0; i < sz; ++i)
        {
            if(nums[i] != i + 1)
                return i + 1;
        }
        return sz + 1;
    }
};

一个长度为n的数列中，如果所有正数都没缺失，那么必然是1,2,3,4...排列，且一个数a的正确位置必定是在a-1处，因此如果A[i]不处在A[A[i] - 1]，那么交换A[i]和A[A[i] - 1]让他去正确位置，由此直到所有该到正确位置的到正确位置，其中<=0和>n的数没有正确位置，所以终止。排好位置后再遍历

手动hash？

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        nums.push_back(0); // 使得每个处于i位置的数对应为i，所以需要多加一个
        int n = nums.size();
        for(auto& num : nums)
        {
            if(num < 0 || num >= n) // 此处需要 >= n 而不是 > n 是因为原数组为n-1长度，那么最大正数为n-1，现在因为加了一个，但是n是不合法的
                num = 0;
        }
        for(auto& num : nums)
        {
            nums[num % n] += n;
        }
        for(int i = 1; i < n; ++i)
        {
            if(nums[i] / n == 0)
                return i;
        }
        return n;
    }
};

引用一段解释[@triton11](https://leetcode.com/triton11/)

So consider an array like [1,4,3,3,3]. The length is 5, so n = 5. For each item, we are basically overwriting the spot at the index of the item with 5 + spot. So, at index 0 we have a 1, and 1%5 is 1, so we replace the item at index 1 with 5 + that item. Now our array is [1,9,3,3,3]. Next, at index 1 we have a 9, and 9%5 is 4 (notice how adding 5 didn't change the fact that we can still find the original value with % 5), so we replace the item at index 4 with 5 + that item. Our array is now [1, 9, 3, 3, 8]. Continuing, we get [1, 9, 3, 8, 8] then [1, 9, 3, 13, 8] and finally [1, 9, 3, 18, 8]. When we iterate through to find the values at the end, starting at index 1, we find that 9/5 is greater than 1, 3/5 is not greater than 1, 13/5 and 8/5 are greater than 1. Thus, since 3/5 is the first not greater than 5, we know index 2 was never used or added to, so 2 is the missing number. Feel free to comment if you have Qs or if I made any mistakes.

一个数加上一个模值后可以通过取余保留其原来的信息，也可以通过其大小显示出频率，如果一个位置的数没被加到，那他就小于模，就是missing的数