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

题目链接

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

题目描述

注意点

• 在不使用额外空间且时间复杂度为 O(n) 的情况下解决这个问题

解答思路

• 要想找到消失的数字需要使用哈希表，因为本题要在不使用额外空间且时间复杂度为 O(n) 的情况下解决这个问题，而所有数字出现的范围为（1，n），所以可以直接使用数组作为哈希表存储数字是否在数组中出现过，具体方法是：第一次遍历根据nums[i]对应的数字x将其对应数组中下标相应值nums[x - 1]加上n，第二次遍历通过nums[i]的值不大于n的下标推出数组中消失的数字
• 在根据数字x将其对应数组中下标相应值nums[x - 1]加上n时，此时x可能已经加上了n作为哈希表存储数字，所以需要将x - 1对n进行取模后再进行存储（因为数字可能重复出现，x可能为nums[i] + n * i，所以不能相减而是取模）

代码

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> res = new ArrayList<>();
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            int x = (nums[i] - 1) % n;
            nums[x] += n;
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] <= n) {
                res.add(i + 1);
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

关键点

• 以原数组作为哈希表存储在数组中出现的数字