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``。题目的进阶要求是在线性时间内仅使用常数额外空间完成,但函数只需返回缺失的单个整数。
自建示例
--------
缺失值位于中间:
.. code-block:: text
输入:nums = [4, 2, 1, 0]
输出:3
解释:数组长度为 4,完整候选集合是 {0, 1, 2, 3, 4},其中只有 3 没有出现。
缺失值是上边界:
.. code-block:: text
输入:nums = [0]
输出:1
解释:n = 1,候选数字是 0 和 1;数组已有 0,因此缺失的是 n 本身。
用异或抵消全集
--------------
数组长度为 ``n`` 时,完整集合是 ``0,1,...,n``。把这些数和数组中的所有数一起异或:
完整集合中出现一次的缺失值只出现一次;数组中实际出现的其他值在两边各出现一次,会按
``x ^ x = 0`` 抵消。可以把循环写成:
.. code-block:: text
missing = n
for i = 0 .. n-1:
missing ^= i ^ nums[i]
初始化为 ``n`` 是为了把全集最后一个元素也纳入计算,不需要额外访问 ``nums[n]``。
正确性说明
----------
循环结束时 ``missing`` 是全集 ``0..n`` 的异或与数组元素异或的结果。除缺失值外,
每个全集元素恰好在这两个来源中出现两次并消失;缺失值只出现一次,故最终结果就是它。
异或不依赖输入顺序,也不会因求和超出整数范围。
C++ 实现
--------
.. code-block:: cpp
class Solution {
public:
int missingNumber(std::vector& nums) {
int missing = static_cast(nums.size());
for (int i = 0; i < static_cast(nums.size()); ++i) {
missing ^= i;
missing ^= nums[i];
}
return missing;
}
};
代码分析
--------
每个数组元素和对应下标只处理一次,时间复杂度为 ``O(n)``,额外空间为 ``O(1)``。
算法不排序、不建立集合,缺失值为 0 或 ``n`` 时也由同一套抵消逻辑处理。