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`` 时也由同一套抵消逻辑处理。