LeetCode DSA 系列 #6: 268. 缺失数字

Source: Dev.to

问题概述

本题是 LeetCode 268. Missing Number —— 给定一个包含 n 个互不相同的数字的数组 nums，这些数字取自区间 [0, n]，请找出数组中缺失的那个数字。

该问题被归类为 Easy（简单）级别。

方法一 – 集合差

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        n = len(nums)

        # 构建完整序列 [0, n] 并转换为集合
        full_set = set(range(n + 1))

        # 缺失的数字是存在于 full_set 但不在 nums 中的元素
        missing = full_set - set(nums)
        return missing.pop()

复杂度

• 时间: O(n) – 构建集合并计算差集时只遍历一次列表。
• 空间: O(n) – 额外的大小为 n + 1 的集合。

方法二 – 暴力搜索

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        n = len(nums)

        # 检查 0 到 n 的每个数字；返回第一个不在 nums 中的数字
        for i in range(n + 1):
            if i not in nums:
                return i

复杂度

• 时间: O(n²) – 最坏情况下 i not in nums 对每个 i 都进行线性搜索。
• 空间: O(1)。

方法三 – 列表删除

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        n = len(nums)

        # 从完整列表 [0, n] 开始，删除在 nums 中出现的每个元素
        sequence = list(range(n + 1))
        for num in nums:
            sequence.remove(num)
        return sequence[0]

复杂度

• 时间: O(n²) – list.remove 为 O(n)，会被调用 n 次。
• 空间: O(n) – 辅助列表 sequence。

更佳解法

1. XOR 方法（O(n) 时间，O(1) 空间）

一个数与自身进行 XOR 得到 0，且 XOR 具备交换律。将所有索引 0…n 与 nums 中的所有元素进行 XOR，结果即为缺失的数字。

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        missing = len(nums)          # 从 n（额外的索引）开始
        for i, num in enumerate(nums):
            missing ^= i ^ num
        return missing

复杂度

• 时间: O(n) – 单次遍历。
• 空间: O(1) – 只使用了少量整数变量。

2. 求和公式（O(n) 时间，O(1) 空间）

前 n 个自然数的和为 n*(n+1)//2。用这个总和减去数组的实际和即可得到缺失的数字。

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        n = len(nums)
        expected_sum = n * (n + 1) // 2
        actual_sum = sum(nums)
        return expected_sum - actual_sum

复杂度

• 时间: O(n) – 计算 sum(nums) 只需一次遍历。
• 空间: O(1)。

XOR 与求和两种方法在常数因子性能上均优于基于集合的方法，同时保持线性时间和常数额外空间。