题解 | 缺失的第一个正整数

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

思路分析
由于要求空间复杂度 O(1)，我们不能使用额外的哈希表，只能利用原数组进行标记。关键思路是
缺失的最小正整数一定在 [1, n+1] 范围内（n 是数组长度）
我们可以通过重新排列数组，让数字 i 出现在位置 i-1 上
遍历重新排列后的数组，第一个位置不满足 nums[i] == i+1 的，i+1 就是缺失的最小正整数

while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) 
{swap(nums[i], nums[nums[i] - 1]);}
1.这里的while循环不可以写成条件判断语句,当我们交换两个元素后，被交换到当前位置的新元素可能也需要继续交换.
2.nums[nums[i] - 1] != nums[i]这是正确的,
这个条件检查的是：数字 nums[i] 是否已经在它应该在的位置上。
nums[i-1] != i（这是有欠缺的）
这个条件检查的是：位置 i-1 上的数字是否等于 i。
但是当数组中有重复元素时,nums[i-1] != i,在 while 循环中可能会发生无限交换(eg.{2,2,3}),而nums[nums[i] - 1] != nums[i]就不会