Vue.js

Appearance

On this page

实战：找到所有数组中消失的数字 ​

前面几道题目，我们都在用额外的数据结构来辅助解题。现在我要问一个问题：能不能不用额外空间，直接在原数组上做文章？

这道题将带你领略一种精妙的技巧——原地标记。

题目描述 ​

LeetCode 448. Find All Numbers Disappeared in an Array

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

示例 1：

输入：nums = [4,3,2,7,8,2,3,1]
输出：[5,6]

示例 2：

输入：nums = [1,1]
输出：[2]

进阶：你能在不使用额外空间且时间复杂度为 O(n) 的情况下解决这个问题吗？

问题分析 ​

首先要问一个问题：这道题的特殊之处在哪里？

仔细观察题目条件：

  • 数组长度为 n
  • 元素值在 [1, n] 范围内

有没有发现什么？值的范围和索引的范围完美对应！

值：    1  2  3  4  5  6  7  8
索引：  0  1  2  3  4  5  6  7
映射：  值 - 1 = 索引

这个特点太重要了。它意味着：每个值都可以"指向"一个唯一的索引位置。

解法一：哈希集合（基础版） ​

最直观的思路：用 Set 记录出现过的数字，再遍历 [1, n] 找缺失的。

javascript
function findDisappearedNumbers(nums) {
  const n = nums.length;
  const seen = new Set(nums);
  const result = [];
  
  for (let i = 1; i <= n; i++) {
    if (!seen.has(i)) {
      result.push(i);
    }
  }
  
  return result;
}

复杂度分析：

  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

这个解法很清晰，但是用了 O(n) 的额外空间。题目的进阶要求是 O(1) 额外空间。

现在我要问第二个问题：能不能利用数组本身来记录"哪些数字出现过"？

解法二：原地标记（进阶版） ​

核心思想 ​

既然值和索引有对应关系，我们可以：

  • 遇到值 val，就在索引 val - 1 处做个"标记"
  • 最后检查哪些位置没被标记，它们对应的值就是缺失的

怎么标记？把那个位置的值变成负数！

为什么用负数？

  • 不丢失原始信息：通过 Math.abs() 随时可以恢复
  • 不冲突：正负可以明确区分"已标记"和"未标记"

代码实现 ​

javascript
function findDisappearedNumbers(nums) {
  const n = nums.length;
  
  // 第一轮：标记出现的数字
  for (let i = 0; i < n; i++) {
    // 取绝对值，因为可能已经被标记为负数
    const idx = Math.abs(nums[i]) - 1;
    
    // 只有正数才标记，防止重复标记变回正数
    if (nums[idx] > 0) {
      nums[idx] = -nums[idx];
    }
  }
  
  // 第二轮：收集未被标记的位置
  const result = [];
  for (let i = 0; i < n; i++) {
    if (nums[i] > 0) {
      // 索引 + 1 就是缺失的数字
      result.push(i + 1);
    }
  }
  
  return result;
}

复杂度分析：

  • 时间复杂度：O(n)
  • 空间复杂度：O(1)（不算返回结果）

执行过程可视化 ​

让我们用示例 [4, 3, 2, 7, 8, 2, 3, 1] 走一遍：

初始状态：  [4, 3, 2, 7, 8, 2, 3, 1]
索引：       0  1  2  3  4  5  6  7

处理 nums[0]=4：
  idx = 4 - 1 = 3
  将 nums[3] 标记为负
  结果：[4, 3, 2, -7, 8, 2, 3, 1]

处理 nums[1]=3：
  idx = 3 - 1 = 2
  将 nums[2] 标记为负
  结果：[4, 3, -2, -7, 8, 2, 3, 1]

处理 nums[2]=-2，绝对值是2：
  idx = 2 - 1 = 1
  将 nums[1] 标记为负
  结果：[4, -3, -2, -7, 8, 2, 3, 1]

处理 nums[3]=-7，绝对值是7：
  idx = 7 - 1 = 6
  将 nums[6] 标记为负
  结果：[4, -3, -2, -7, 8, 2, -3, 1]

处理 nums[4]=8：
  idx = 8 - 1 = 7
  将 nums[7] 标记为负
  结果：[4, -3, -2, -7, 8, 2, -3, -1]

处理 nums[5]=2：
  idx = 2 - 1 = 1
  nums[1] 已经是负数，跳过

处理 nums[6]=-3，绝对值是3：
  idx = 3 - 1 = 2
  nums[2] 已经是负数，跳过

处理 nums[7]=-1，绝对值是1：
  idx = 1 - 1 = 0
  将 nums[0] 标记为负
  结果：[-4, -3, -2, -7, 8, 2, -3, -1]

最终状态：[-4, -3, -2, -7, 8, 2, -3, -1]
                          ↑  ↑
                       索引4 索引5 仍为正数

索引4对应的值是 5，索引5对应的值是 6
输出：[5, 6]

关键细节解析 ​

为什么要取绝对值？ ​

因为我们会把数组元素改成负数，后面遍历到这个位置时，要用它的原始值来计算索引：

javascript
// ❌ 错误：如果 nums[i] 已经被改成负数，直接减1会出错
const idx = nums[i] - 1;  // 负数减1得到错误的索引

// ✅ 正确：取绝对值恢复原始值
const idx = Math.abs(nums[i]) - 1;

为什么要检查是否大于0？ ​

防止重复元素导致同一个位置被标记两次：

javascript
// ❌ 危险：直接取反，如果执行两次会变回正数
nums[idx] = -nums[idx];  // 第一次：正→负，第二次：负→正

// ✅ 安全：只有正数才标记
if (nums[idx] > 0) {
  nums[idx] = -nums[idx];
}

边界情况 ​

  • 空数组：直接返回空数组
  • 无缺失：如 [1, 2, 3]，所有位置都被标记，返回空数组
  • 全缺失：如 [1, 1, 1]，只有索引0被标记，返回 [2, 3]

拓展思考 ​

相关题目 ​

这种"原地标记"技巧在多道题目中都有应用：

  • LeetCode 442：找出数组中所有重复的数字
  • LeetCode 41：缺失的第一个正数（Hard）

另一种标记方式 ​

除了用负数标记，还可以用"加 n"的方式：

javascript
function findDisappearedNumbers(nums) {
  const n = nums.length;
  
  // 标记：遇到的值对应位置加n
  for (let i = 0; i < n; i++) {
    const idx = (nums[i] - 1) % n;  // 取模恢复原始索引
    nums[idx] += n;
  }
  
  // 收集：值 <= n 的位置就是缺失的
  const result = [];
  for (let i = 0; i < n; i++) {
    if (nums[i] <= n) {
      result.push(i + 1);
    }
  }
  
  return result;
}

本章小结 ​

这道题的核心洞察是：当值的范围和索引范围对应时，可以把数组本身当作哈希表。

通过原地标记：

  • 将 O(n) 空间优化到 O(1)
  • 利用正负号编码"是否出现过"的信息
  • 取绝对值可以随时恢复原始值

这种"索引即信息"的思维方式，在算法题中非常有用。当你看到"值在 [1, n] 范围内"这样的条件时，就要想到可能可以用原地标记。

在 GitHub 上编辑此页