跳到主要内容

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

1. 题目简介​

难度:简单,原题链接:448. 找到所有数组中消失的数字。

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

进阶:你能在不使用额外空间且时间复杂度为 O(n) 的情况下解决这个问题吗? 你可以假定返回的数组不算在额外空间内。

2. 问题分析​

这道题需要记录 1 到 n 中哪些数字出现过,再找出没有出现的数字。直接的办法是申请一个长度为 n 的布尔数组:数字 t 出现时,就把下标 t - 1 标记为 true,最后收集没有标记的位置。

要省去这个辅助数组,可以把标记保存在 nums 自己的位置上。题目给出了范围:

1 <= nums[i] <= n

每遇到数字 t,就给 nums[t - 1] 加上 n。原始值最多为 n,只要这个位置被加过,值就会超过 n。全部处理完后,仍满足 nums[i] <= n 的位置就没有被标记过,对应的 i + 1 是缺失数字。

修改数组时,还必须保留读取原始数字的办法。当前的 nums[i] 可能已经被其他数字标记过,因此不能直接拿它当下标。先用 (nums[i] - 1) % n,就能去掉累加的 n,得到原始数字对应的下标。

例如 n = 4,某个位置原来是 3,被标记两次后变成 11,(11 - 1) % 4 仍然是 2,也就是数字 3 应当标记的位置。

3. 代码实现​

class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
int n = nums.length;
for (int i = 0; i < n; i++) {
// 1. 数字 t 对应的数组下标为 t - 1
// 2. 当前元素可能已经被变换过,所以需要取模
int tmp = (nums[i] - 1) % n;
nums[tmp] += n;
}
List<Integer> res = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
if (nums[i] <= n) {
res.add(i + 1);
}
}
return res;
}
}

4. 复杂度分析​

  • 时间复杂度:O(n),两次扫描分别标记出现情况和收集缺失数字。
  • 额外空间复杂度:O(1),按题目约定不计算返回结果所占空间;标记会修改输入数组。

来源:Coding 101 原文 · 免费阅读,引用请保留出处。内容使用说明