LeetCode448：找到所有数组中消失的数字

要求

给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。

思路

可以把数组中的元素与索引建立一一对应的关系。因为索引是确定的0到n-1，nums[i] 在区间 [1, n] 内；既然两者是一一对应的关系，那么我们对数组中的每个元素对应的索引做个标记；

蓝色数字：应该出现在当前位置的数字
红色数字：实际出现在当前位置的数字，可以把当前位置元素’*-1’，变成负数，方便遍历寻找缺数
应该出现在当前位置的数字 = 元素索引下标 + 1

代码实现的思路：
1、遍历每个元素，对索引进行标记

• 将对应索引位置的值变为负数；

2、遍历下索引，看看哪些索引位置上的数不是负数的。

• 位置上不是负数的索引，对应的元素就是不存在的。

public List<Integer> findDisappearedNumbers(int[] nums) {
    //建立一个List用来存放结果
    List<Integer> res = new ArrayList<>();
    //遍历nums数组，对对应的索引位置的元素做标记
    for (int i = 0; i < nums.length; i++) {
        //由于当前位置数组元素可能已经被*-1了，所以取绝对值
        int abs = Math.abs(nums[i]);
        //如果当前索引下标 i 位置的数组元素的值 abs-1 作为索引下标的元素值
        if (nums[abs - 1] > 0){
            nums[abs - 1] *= -1;
        }
    }

    //遍历数组中元素大于的0的元素下标，此时位置索引下标+1就是缺失的元素
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] > 0){
            res.add(i + 1);
        }
    }
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21