2022-04-16.md

每日一题 - 找到所有数组中消失的数字

信息卡片

• 时间：2022-04-16
• 题目链接：https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/
• tag：数组 哈希表

题目描述

给你一个含 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]

提示：

• $n == nums.length$
• $1 <= n <= 10^5$
• $1 <= nums[i] <= n$

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

思路分析

1. 引入 哈希map 记录，再通过检索哪些数字没出现。空间复杂度 $O(n)$ 超出了进阶要求
2. 使用数组本身，其长度为n，而且数字范围在[1, n]，所以可以利用这个范围之外记录数字是否出现过
3. 故使数组中所有数加某个值、或者都为负数

参考答案

改变原数值，使数字 变成负数 | 累加

• 时间复杂度：$O(n)$
• 空间复杂度：满足在当前数组内

负数：

1. i → 4
   • 4 - 1 = 3
   • nums[3] = -nums[3]（7 → -7）
2. i → 3（i++）
   • 3 - 1 = 2
   • nums[2] = -nums[2]（2 → -2）
3. 因为当前元素可能被修改，后续取下标时 需要还原
4. ...
5. 遍历结束，只有 nums[4]（8） 和 nums[5]（2）非负数
6. 下标+1：[4 + 1 = 5, 5 + 1 = 6]，所以缺少 [5, 6]

function findDisappearedNumbers(nums) {
  let result = []
  const len = nums.length
  for (let i = 0; i < len; i++) {
    let index = Math.abs(nums[i]) - 1
    if (nums[index] > 0) {
      nums[index] = -nums[index]
    }
  }
  for (let i = 0; i < len; i++) {
    if (nums[i] > 0)
    result.push(i + 1)
  }
  return result
}

累加：

• 考虑累加后的和不能在数组中出现过，所以 +n 可以保证数值范围：[n+1, 2n]

function findDisappearedNumbers(nums) {
  let result = []
  const len = nums.length
  // O(n)
  for (let i = 0; i < len; i++) {
    // 对n取模来还原本来的值（可能累加过）
    let index = (nums[i] - 1) % len
    nums[index] += len
  }
  // O(n)
  for (let i = 0; i < len; i++) {
    if (nums[i] <= len) {
      result.push(i + 1)
    }
  }
  // O(n) + O(n) = O(2n) => O(n)
  return result
}

综上：两种方法思路是一致的，只在 改变和还原数值时不同