LeetCode 面试题 17.04. 消失的数字

约 3 分钟
文章信息 3 个分类 5 个标签
分类
LeetCode 简单 程序员面试金典（第 6 版）
标签
数组 哈希表 数学 排序 位运算

题目描述

✅ 面试题 17.04. 消失的数字

image-20260929010441177

题意分析

数组长度为 n，其中是 0..n 范围内的 n 个互不相同的数，恰好缺少一个，返回这个缺失值。完整范围比数组多一个元素，缺失值可能是 0，也可能是 n。

解法：全集与已知元素异或抵消

核心思路

[!blue]

异或满足 x ^ x = 0、x ^ 0 = x，并且交换、重排运算顺序不影响结果。如果把完整范围 0..n 和数组中的所有值一起异或，每个已出现的值都有两份，会彼此抵消；缺失值只在完整范围中出现一次，最终就留下它。

不需要额外生成完整范围：遍历数组时，下标 i 已经依次给出 0..n-1，只比完整范围少了 n。因此先令 answer = n，每轮执行 answer ^= i ^ nums[i]，同时加入一项全集值和一项已知值。

扫描结束后，所有应当抵消的值都已经成对加入，answer 就是缺失值。数组原来的排列顺序无关紧要，也不需要修改输入；缺失 0 或 n 都自然包含在同一个抵消过程里。

解题步骤

  1. 读取数组长度 n，令 answer = n，先补上完整范围的最后一项。
  2. 遍历每个下标 i，将 i 和对应数组值一起异或到答案中。
  3. 全部元素处理完后返回 answer。

代码实现

class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        // 初值取 n，补上全集 0..n 相对下标 0..n-1 多出来的那一项。
        int answer = n;

        for (int i = 0; i < n; ++i) {
            answer ^= i ^ nums[i];
        }

        return answer;
    }
}

func missingNumber(nums []int) int {
    n := len(nums)
    // 初值取 n，补上全集 0..n 相对下标 0..n-1 多出来的那一项。
    answer := n

    for i, v := range nums {
        answer ^= i ^ v
    }

    return answer
}

复杂度分析

  • 时间复杂度：$O(n)$。每个下标和数组值各参与一次异或。
  • 空间复杂度：$O(1)$。只保存长度、下标和累计异或值。

关键点总结

[!green]

  • 完整范围负责提供每个值的一份，数组再提供所有已出现值的另一份。
  • 下标已经覆盖 0..n-1，初值 n 补足全集。
  • 异或只消掉成对出现的值，不依赖排序，也没有求和时的中间总量问题。

易错点总结

[!yellow]

  • 初值若设为 0 又没有额外异或 n，就漏掉了完整范围的一项。
  • 必须同时加入下标和值，只异或数组本身无法让所有已出现值成对抵消。
  • 互不相同、范围恰为 0..n、只缺一个数是证明前提，不能把此方法直接用于含重复或缺多个值的输入。

相似题目

题目 难度 关联与区别
136. 只出现一次的数字 简单 同样让成对值异或抵消，原题的成对来自输入，本题先补出完整范围的一份。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/47753199
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！