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

题目描述

题解

抽屉原理

这道题跟41题几乎是一模一样的思路, 就是通过原地哈希, 将所有的元素都摆放到其对应的位置, 即1放在索引为0处, 2放在索引为1处…

遍历交换位置后的数组, 将所有对不上的元素添加到列表中即可

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

    for (int i = 0; i < nums.length; i++) {
        if (nums[i] != i + 1) {
            res.add(i + 1);
        }
    }

    return res;
}

private void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}