跳到主要内容

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

题目描述​

给你一个含 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，数字范围是 1~n，每个数字出现 1 次或 2 次。需要找出没出现的数字。关键问题是：如何在不使用额外空间的情况下标记数字是否出现？

第二步：哈希表解法​

使用集合记录出现的数字，然后遍历 1~n 找出缺失的。

缺点：需要 O(n) 额外空间。

第三步：原地哈希（最优）​

核心洞察：

  • 数字 num 对应索引 num - 1
  • 将出现过的数字对应位置的值增加 n
  • 最后值仍 <= n 的位置就是没出现过的数字

为什么正确：

  • 每个 num 会让 nums[num - 1] 增加 n
  • 原本的值范围是 1~n，增加后 > n 的位置表示该数字出现过
  • 使用 % n 是为了防止多次加 n 后索引计算出错

完整代码实现​

from typing import List


class Solution:
    """
    找到所有数组中消失的数字 - 原地哈希

    将出现过的数字对应位置的值增加 n
    值仍 <= n 的位置就是没出现过的数字

    时间复杂度：O(n)
    空间复杂度：O(1)（不计输出空间）
    """

    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        n = len(nums)
        for num in nums:
            x = (num - 1) % n  # 计算该数字对应的索引
            nums[x] += n         # 标记该数字出现过

        # 值仍 <= n 的位置，说明对应的数字(i+1)没有出现过
        return [i + 1 for i, num in enumerate(nums) if num <= n]

示例推演​

以 nums = [4,3,2,7,8,2,3,1] 为例，n=8：

步骤numx=(num-1)%8操作nums 状态
初始---[4,3,2,7,8,2,3,1]
143nums[3]+=8[4,3,2,15,8,2,3,1]
232nums[2]+=8[4,3,10,15,8,2,3,1]
321nums[1]+=8[4,11,10,15,8,2,3,1]
476nums[6]+=8[4,11,10,15,8,2,11,1]
587nums[7]+=8[4,11,10,15,8,2,11,9]
621nums[1]+=8[4,19,10,15,8,2,11,9]
732nums[2]+=8[4,19,18,15,8,2,11,9]
810nums[0]+=8[12,19,18,15,8,2,11,9]

最终检查：索引 4 和 5 的值 8 和 2 都 <= 8，对应数字 5 和 6。

答案：[5, 6]

复杂度分析​

解法时间复杂度空间复杂度说明
哈希表O(n)O(n)使用额外集合
原地哈希（最优）O(n)O(1)原地修改数组

易错点总结​

1. 使用 % n​

原因：某些数字可能出现两次，导致 nums[x] 增加多次 n。使用 % n 确保索引计算正确。

2. 原数组被修改​

原地哈希会修改输入数组，如果后续还需要使用原数组，需要先复制。

相关题目​

加载评论中...