LeetCode 268. 丢失的数字

2023-08-22 HGNULB 约 4 分钟

文章信息 15 个分类 8 个标签

分类

LeetCode CodeTop 简单未解决 10-20 字节跳动微软美团阿里巴巴快手腾讯百度滴滴京东虾皮

题目描述

✅ 268. 丢失的数字

题意分析

输入是一个长度为 n 的数组，里面装着 [0, n] 这 n + 1 个整数中的 n 个，且互不重复，要求输出唯一缺席的那一个。注意范围上界是 n 而不是 n - 1：数组有 n 个坑，候选值却有 n + 1 个，正好差一个，缺失值唯一。

约束里最重要的信号有三条。第一，元素互不相同，所以不存在「同一个数出现两次挤掉别人」的干扰，缺失的恰好一个。第二，值域被死死钉在 [0, n]，n 又等于数组长度，这意味着「应该有哪些数」是完全已知的，问题从「搜索」退化成「已知全集减去已有集合」。第三，题目进阶明确要求线性时间、常数额外空间，等于直接封杀了排序（$O(n \log n)$）和哈希集合（$O(n)$ 空间）这两条最省事的路。

边界上要注意：数组可能只有一个元素，此时答案要么是 0 要么是 1；缺失值可能是范围的两个端点 0 或 n，很多写法恰恰在这两处翻车；数组本身无序，不能假设 nums[i] 和下标有任何对应关系。

解法：异或抵消

核心思路

候选全集是 0..n，数组中除缺失值外，每个候选数都恰好出现一次。把全集和数组一起异或，利用 x ^ x = 0、x ^ 0 = x 以及交换律、结合律，所有出现两次的数都会抵消，最后只剩缺失值。

实现时令 ans = n，循环中同时异或下标 i 和元素 nums[i]。下标覆盖 0..n-1，再加上初值 n，正好组成完整候选集，无需额外一趟循环。

循环不变量：处理完前 i 个元素后，ans 等于 n、下标 0..i-1 和数组元素 nums[0..i-1] 的异或结果。循环结束时，每个非缺失值分别来自候选集和数组，成对抵消；缺失值只来自候选集，因此 ans 就是答案。相比求和法，异或不会产生更大的中间值，也就没有整数溢出问题。

解题步骤

设 n = nums.length，初始化 ans = n，先补上候选集中唯一没有对应下标的 n。

遍历数组，对每个位置执行 ans ^= i 和 ans ^= nums[i]。

遍历结束后返回 ans。

以 [3,0,1] 为例，初始 ans = 3，依次合入 (0,3)、(1,0)、(2,1) 后得到 2。候选集中的 0、1、3 都和数组中的同值元素抵消，只有缺失的 2 留下。

代码实现

class Solution {
    public int missingNumber(int[] nums) {
        int ans = nums.length;
        for (int i = 0; i < nums.length; i++) {
            // 下标和数组值中成对出现的数字会被异或抵消。
            ans ^= i;
            ans ^= nums[i];
        }
        return ans;
    }
}

func missingNumber(nums []int) int {
    ans := len(nums)
    for i, num := range nums {
        // 只出现一次的那个范围数字就是缺失值。
        ans ^= i
        ans ^= num
    }
    return ans
}

复杂度分析

时间复杂度：$O(n)$，只遍历数组一次。

空间复杂度：$O(1)$，只使用常数个变量。

关键点总结

将候选全集与实际数组做异或，成对值抵消，缺失值落单。

ans 必须初始化为 n，因为循环下标只能提供 0..n-1。

数组无须有序；异或的交换律和结合律保证遍历顺序不影响结果。

面试中可以对比求和法：两者都是 $O(n)$ 时间、$O(1)$ 空间，但异或没有中间和溢出的风险。

易错点总结

把 ans 初始化为 0 会漏掉候选值 n；如 [0,1] 的答案应为 2。

只异或数组值、不异或下标，无法构造完整候选集。

写成 ans = i ^ nums[i] 会覆盖此前结果，必须使用累计异或 ^=。

题目没有保证数组有序，不能直接用 nums[i] == i 做二分判断。

若改用求和法，扩展到更大数据范围时应使用足够宽的整数类型，避免 n * (n + 1) 先溢出。

相似题目

题目	难度	考察点
面试题 17.04. 消失的数字	简单	同款异或抵消求单个缺失
面试题 17.19. 消失的两个数字	困难	按低位分组分离两个缺失值
136. 只出现一次的数字	简单	成对元素中挑出落单元素
剑指 Offer 53 - II. 0～n-1中缺失的数字	简单	有序前提下二分定位断点
448. 找到所有数组中消失的数字	简单	原地打负号标记求多个缺失
645. 错误的集合	简单	同时求出重复值与缺失值
41. 缺失的第一个正数	困难	值域无界时的原地哈希置换