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

发表于
本文字数： 1.5k 阅读时长 ≈ 1 分钟

LeetCode每日一题，438. Find All Numbers Disappeared in an Array

先看题目描述

yr8FrF.png

大意就是给定一个数组 nums，这个数组的元素个数为 n，其中每个元素的值也在 1 到 n 之间，让我们返回 [1, n] 中所有未在数组 nums 中出现过的元素

算法和思路

计数

第一反应就是计数，创建一个频次数组 cnt，遍历一次 nums 数组，对其中的元素进行计数，cnt[i] 就代表值 i 在 nums 中的出现次数，然后遍历 cnt 数组，若某元素的出现次数为 0，则将其添加至结果列表 res 中，最后返回 res

原地修改

后来去看题解，才看到题目要求不使用额外空间，要原地修改 nums 数组来做

由于 nums 的数字范围均在 [1,n] 中，我们可以利用这一范围之外的数字，来表达「是否存在」的含义

具体来说，遍历 nums，每遇到一个数 x，就让 nums[x−1] 增加 n。由于 nums 中所有数均在 [1,n] 中，增加以后，这些数必然大于 n。最后我们遍历 nums，若 nums[i] 小于等于 n，就说明没有遇到过数 i+1。这样我们就找到了缺失的数字

注意，当我们遍历到某个位置时，其中的数可能已经被增加过，因此需要对 n 取模来还原出它本来的值

算法源码

计数

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

原地修改

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