41. 缺失的第一个正数

题目链接：41. 缺失的第一个正数 (opens new window)

计数数组或者哈希遍历的方法就不说了，空间复杂度会比较高，这里给一个空间复杂度O(1)的解法，也就是在原数组的基础上实现

首先要明白，长度为n的数组，缺失的第一个正数一定在[1,n+1]范围内。那我们就可以用数组的索引来表示某个正数是否出现过，索引[0,n-1]分别对应[1,n],如果每个索引都已出现，那没出现的就是n+1。那该如何用索引表示某个正数是否出现过？数组中原本的负数是无用信息，因为我们要找没有出现过的正数，因此数组中的负数我们可以直接覆盖，所以这里我们把出现过的正数对应的索引值置为负数，而原本的负数我们置为n+1。

还有个问题，比如nums = [3,4,-1,1]，首先处理负数[3,4,5,1]，我们处理完前两个数字后改为[3,4,-5,-1],这里第三第四个数内容被我们置为负数了，所以在确认值在索引范围内时要取绝对值，第四个|1|<4，所以数组变成[-3,4,-5,-1],最后我们就可以确认1,4，在数组中出现过1,3,4。

还有个问题，比如nums = [3,3,-1,1]，首先处理负数[3,3,5,1]，我们处理完第一个数组变为[3,3,-5,1]，处理第二个变为[3,3,5,1],因为有重复的数导致第三个数又被置为正数了，我们在最终遍历的过程中识别到正数是被当做没有出现过的，但其实出现过而且出现了两次。所以我们将特定位置置为负数，不是取相反数，而是对绝对值取负。代码如下：

class Solution {
    public int firstMissingPositive(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] <= 0)
                nums[i] = nums.length + 1;
            System.out.println(nums[i]);
        }
        for (int i : nums) {
            System.out.println(i);
            if (Math.abs(i) <= nums.length) {
                nums[Math.abs(i) - 1] = -Math.abs(nums[Math.abs(i) - 1]);
                // 括号里的abs是防止之前的操作已经把i置为负数了，比如[3,4,-1,1]，会把-1先置为5再置为-5
                /*
                  括号外的abs是为了防止有重复的数，比如[3,3,-1,1]，-1被置为5后，遍历到第一个3为被置为-5，
                  如果不加abs遍历到第二个3就会又被置为正数5，这样读出来的结果3是缺失的，但实际上3是出现了并且出现两次
                 */
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0)
                return i + 1;
        }
        return nums.length + 1;
    }
}