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

理想情况下每个元素都在自己的位置上，如下：

现在将元素对应位置打乱，并且缺失了一个元素，如下：

那么怎么找到这个缺失元素呢？我们可以依次遍历数组 nums ，每遍历到一个元素，比如 nums[i] ，就将 nums[i] 的值对应的位置做上标记，表示这个位置上的主人出现过，只是现在不在这个位置。遍历结束后，如果某个位置上没有被标记，说明这个位置上的主人缺失了。

`
nums[1] = 3，将3这个位置做标记。

nums[2] = 1，将1这个位置做标记。

nums[3] = 5，将5这个位置做标记。

nums[4] = 1，将1这个位置做标记。

nums[5] = 6，将6这个位置做标记。

nums[6] = 4，将4这个位置做标记。

可以看到，最后 2 位置上是没有被标记的，所以 2 就是缺失元素。
怎么标记呢？对这一题，我们要找的是一个正数，所以如果 nums[i] <= 0 ，那么我们不用管，将它映射到 [1, n] 之外，所以我们先遍历一次数组将 负数 和 0 映射成 n + 1 （只要大于n都行）。
再一次遍历数组，每遍历到一个元素 nums[i] ，先判断它是否大于 n ，若大于，说明它原先是小于等于 0 的数，则忽略，继续往后遍历。若小于 n ，则将 nums[i] 的值对应的位置上的元素变为原来的相反数，即 nums[nums[i]] = -nums[nums[i]] ，相当于上面的绿色标记，如下： 下标为 1 的元素值为 3 ，将 3 这个位置做标记（值取相反数）。

为什么要变成原来的相反数呢？因为这样方便我们获取它原来的值（只需取绝对值）。比如，当我们遍历到下标 3 这个位置时，我们只需要对 nums[3] 取绝对值就可以获取它原来的值 5 ，然后将 5 这个位置上做上标记（取相反数）。如下：

遍历结束之后，如果有某个位置上还是大于 0 的，说明该位置是缺失元素。

==========================================================================
2022-7-26更新
上述取 相反数 改为 取 绝对值的相反数 ，原因是如果一个位置上的数出现两次，会被取两次相反数，而变为正数。比如上图中的 1 位置上的 3 。代码已更新

public class Solution {
    public int minNumberDisappeared (int[] nums) {
        int n = nums.length;
        // 第一轮遍历，将小于等于0的数忽略（映射到n之外）
        for(int i = 0; i < n; i++){
            if(nums[i] <= 0){
                nums[i] = n + 1;
            }
        }
        // 第二轮遍历，做标记
        for(int i = 0; i < n; i++){
            if(Math.abs(nums[i]) <= n){
                nums[Math.abs(nums[i]) - 1] = -Math.abs(nums[Math.abs(nums[i]) - 1]);
            }
        }
        // 第三轮遍历，找到没被标记的位置
        for(int i = 0; i < n; i++){
            if(nums[i] > 0){
                return i + 1;
            }
        }
        return n + 1;
    }
}