LeetCode 268. 丢失的数字

约 4 分钟
文章信息 15 个分类 6 个标签
分类
LeetCode CodeTop 简单 未解决 10-20 腾讯 字节 阿里 微软 美团 京东 百度 快手 滴滴 虾皮
标签
数组 哈希表 数学 排序 二分查找 位运算

题目描述

✅ 268. 丢失的数字

image-20260928215921689

image-20260928215921690

题意分析

数组长度为 n，包含 0 到 n 范围内的 n 个互不相同的整数。完整范围一共有 n + 1 个数，因此恰好缺少一个，返回这个没有出现的值。

缺失值可能是零、范围中间的数，也可能是上界 n。数组没有保证有序，但保证已有元素互不重复且都在范围内。进阶要求线性时间和常数额外空间，因此不能依赖额外集合记录全部出现情况。

解法：异或抵消

核心思路

[!blue]

异或满足三个性质：相同的数异或为零，零与某个数异或仍是这个数，而且交换顺序或改变分组不会影响结果。只要让完整候选范围 0..n 与数组中的全部值一起参与异或，已经存在的每个值就会出现两次并抵消，缺失值只出现一次，最后留下的就是它。

不需要另外建立候选数组。遍历输入时，下标 i 已经依次提供了 0..n - 1，唯一缺少的候选是 n，所以先令 ans = n。每轮再把当前下标 i 和当前数组值 nums[i] 一起异或到 ans 中，就同时枚举了候选与实际值。

下标和同位置的数组值不必相等，它们也不需要当场抵消。交换律与结合律允许把不同轮次出现的相同值配在一起，因此输入的排列顺序不影响答案。

循环结束时，ans 等于完整候选集合与实际数组的累计异或。若缺失的是零，其他值全部抵消后结果就是零；若缺失的是 n，初始化时放入的 n 没有对应值可抵消，也会被正确保留。整个过程只读输入，不需要排序或求和。

解题步骤

  1. 令 ans = nums.length，先加入候选范围的上界 n。
  2. 遍历每个下标 i，执行 ans ^= i，加入对应候选值。
  3. 再执行 ans ^= nums[i]，加入实际出现的值。
  4. 遍历完成后返回累计结果 ans。

代码实现

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)$，只保存累计异或值和循环下标，不修改输入。

关键点总结

[!green]

  • 把完整候选范围与实际出现值合在一起，使已有值成对抵消。
  • 下标提供 0..n - 1，初始化为 n 补全候选范围。
  • 异或抵消依赖题目保证的值域与唯一性，与输入是否有序无关。

易错点总结

[!yellow]

  • 将 ans 初始化为零却没有另外加入 n，会漏掉候选范围的最后一个数。
  • 只异或输入元素，没有加入完整候选范围，无法保证已有值都成对抵消。
  • 使用赋值 ans = i ^ nums[i]，会丢掉此前轮次的结果；这里需要累计异或。
  • 因为候选范围有序，就直接对输入使用下标与值的二分判断；输入数组本身并不保证有序。
  • 将“缺失零时结果为零”当成无答案，混淆合法数值与失败标记；本题保证缺失值一定存在。

相似题目

题目 难度 关联与区别
136. 只出现一次的数字 简单 同样靠相同值异或抵消，本题需补上完整范围中的每个值。
260. 只出现一次的数字 III 中等 维护异或抵消关系定位少数异常值；本题将下标与数值异或以找缺失值，该题用非零位分成两组分别抵消。
389. 找不同 简单 维护异或抵消关系定位少数异常值；本题将下标与数值异或以找缺失值，该题异或两个字符串以找新增字符。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2023/24852054
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！