0268. Missing Number

题目信息

题号:

0268

难度:

Easy

主题:

数组、集合缺失值、数学、位运算

原题:

LeetCode 0268

重点:

候选全集是 0..n、数组只包含其中互不相同的 n 个数、缺失值也可能是边界 n

题目重述

给定长度为 n 的整数数组 nums。候选数字全集是从 0 到 n 的 n+1 个整数,而数组恰好包含其中 n 个互不相同的值。返回唯一没有出现在数组中的那个整数。

n 位于 [1, 10^4],每个 nums[i] 位于 [0, n],并且所有数组元素两两不同。输入顺序没有任何保证,缺失值既可能位于中间,也可能是 0 或 n。题目的进阶要求是在线性时间内仅使用常数额外空间完成,但函数只需返回缺失的单个整数。

自建示例

缺失值位于中间:

输入:nums = [4, 2, 1, 0]
输出:3
解释:数组长度为 4,完整候选集合是 {0, 1, 2, 3, 4},其中只有 3 没有出现。

缺失值是上边界:

输入:nums = [0]
输出:1
解释:n = 1,候选数字是 0 和 1;数组已有 0,因此缺失的是 n 本身。

用异或抵消全集

数组长度为 n 时,完整集合是 0,1,...,n。把这些数和数组中的所有数一起异或: 完整集合中出现一次的缺失值只出现一次;数组中实际出现的其他值在两边各出现一次,会按 x ^ x = 0 抵消。可以把循环写成:

missing = n
for i = 0 .. n-1:
    missing ^= i ^ nums[i]

初始化为 n 是为了把全集最后一个元素也纳入计算,不需要额外访问 nums[n]。

正确性说明

循环结束时 missing 是全集 0..n 的异或与数组元素异或的结果。除缺失值外, 每个全集元素恰好在这两个来源中出现两次并消失;缺失值只出现一次,故最终结果就是它。 异或不依赖输入顺序,也不会因求和超出整数范围。

C++ 实现

class Solution {
public:
    int missingNumber(std::vector<int>& nums) {
        int missing = static_cast<int>(nums.size());
        for (int i = 0; i < static_cast<int>(nums.size()); ++i) {
            missing ^= i;
            missing ^= nums[i];
        }
        return missing;
    }
};

代码分析

每个数组元素和对应下标只处理一次,时间复杂度为 O(n),额外空间为 O(1)。 算法不排序、不建立集合,缺失值为 0 或 n 时也由同一套抵消逻辑处理。