448. Find All Numbers Disappeare

给出一个整数数组，范围是1 ≤ a[i] ≤ n(n是数组的长度)，数组里有些元素出现了两次，有些出现了一次，找出[1,n]的数组里没有出现的数字。要求是不能用额外的空间，时间复杂度为O(n)。
这里先说一下我的解法吧（很辣鸡就是了hhhh）

public List<Integer> findDisappearedNumbers(int[] nums) {
    List<Integer> result = new ArrayList<>();
    if (nums.length == 0) {
        return result;
    }
    Arrays.sort(nums);
    int last = nums.length;
    int index = 0, i;
    for (i = 1; i <= last && index < last;) {
        if (nums[index] == i) {
            index +=1;
            i += 1;
            continue;
        } else if (nums[index] < i) {
            index++;
            continue;
        } else {
            result.add(i);
            i++;
         }
      }
      for (; i <= last; i++) {
          result.add(i);
      }
      return result;
}

这里存在三种情况，缺的数在起始端、中间、末尾，而且存在重复的数字。我采用的方法是先对数组进行排序，再从头开始进行对比。代码我个人认为还是比较好理解的。如果相同，进行下一次对比，如果数组里的数小于i，说明这个数是重复的，可以跳过。最后的一个for循环是处理类似[1,1,2,2]这样缺的数在末尾的情况。其实我觉得Arrays.sort的复杂度应该是O(nlgn)的。。。

辣鸡代码就看到这里，接下来看Top Solution里的几种解法。
第一种：

public List<Integer> findDisappearedNumbers(int[] nums) {
    List<Integer> ret = new ArrayList<>();
    
    for (int i = 0; i < nums.length; i++) {
        int val = abs(nums[i]) - 1;
        if (val > 0) {
            nums[val] = -nums[val];
        }
    }
    
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] > 0) {
            ret.add(i+1);
        }
    }
}

这种解法的思路是：如果一个数组为[1,2,3....n]，那么通过一次迭代使nums[nums[i]-1] = -nums[nums[i]-1]之后，数组里的所有数都应该为负值，此时我们再进行第二次迭代，若某个下标对应的值不为负数，那么该下标+1的值就是缺少的值。
再来看第二种：思路与上一种类似，这次是在第一次迭代时进行nums[(nums[i]-1) % n] += n的操作，这样一轮迭代之后，如果某一个下标对应的值小于n，那么该下标+1的值就是缺少的值。
第三种方法是进行交换：如果nums[i] != i + 1 && nums[i] != nums[nums[i]-1]就将nums[i]与nums[nums[i]-1]进行交换，nums[i] != nums[nums[i]-1]这个条件是判断这个数是否是重复的数字，最后再扫描一遍数组，如果下标+1不等于nums[i]的值，下标+1就是缺少的那个数，代码如下

public List<Integer> findDisappearedNumbers(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        while (nums[i] != i + 1 && nums[i] != nums[nums[i] - 1]) {
            int temp = nums[i];
            nums[i] = nums[temp - 1];
            nums[temp - 1] = temp;
        }
    }
    List<Integer> res = new ArrayList<>();
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] != i + 1) {
            res.add(i + 1);
    }
    return res;
}

拿示例数组[4, 3, 2, 7, 8, 2, 3, 1]来说吧，作者给出了完整的运行过程，可以帮助理解

[4,3,2,7,8,2,3,1]
[7,3,2,4,8,2,3,1]
[3,3,2,4,8,2,7,1]
[2,3,3,4,8,2,7,1]
[3,2,3,4,8,2,7,1]
[3,2,3,4,1,2,7,8]
[1,2,3,4,3,2,7,8]

还有用Python一行搞定的。。不懂Python所以没有看，有兴趣可自行阅读。