448. 找到所有数组中消失的数字（高频题）

448. 找到所有数组中消失的数字

• 解题思路
• 代码

解题思路

将所有正数作为数组下标，置对应数组值为负值。那么，仍为正数的位置即为（未出现过）消失的数字。

举个例子：

• 原始数组：[4,3,2,7,8,2,3,1]

• 重置后为：[-4,-3,-2,-7,8,2,-3,-1]

结论：[8,2] 分别对应的index+1后为[5,6]（消失的数字）

代码

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> list = new ArrayList<>();
        //将所有正数作为数组下标，置对应数组下标元素的值为负值。
        //最后仍为正数的位置即为（未出现过）消失的数字。
        for (int i = 0; i < nums.length; i++) {
            //由于有的数字是重复的，所以当该数字已经被置为负数时则nums[Math.abs(nums[i]) - 1] < 0不再处理
            if (nums[Math.abs(nums[i]) - 1] > 0) {
                nums[Math.abs(nums[i]) - 1] = -nums[Math.abs(nums[i]) - 1];
            }
        }
        //将仍为正数的索引+1记录下来
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) list.add(i + 1);
        }
        return list;
    }
}