0136. Single Number =================== 题目信息 -------- :题号: 0136. 只出现一次的数字 :难度: Easy :主题: 数组、位运算、异或归约、常量空间 :原题: `LeetCode 0136 `_ :重点: 利用其余元素恰好成对出现的强条件,让异或同时承担计数奇偶性与答案累积 题目重述 -------- 给定非空整数数组 ``nums``,恰有一个元素只出现一次,其余每个元素都恰好出现两次。返回这个单次元素。 要求算法在线性时间内完成,并只使用常量级额外空间。 自建示例 -------- * ``nums = [11, -2, 7, 11, 7]``:``11`` 和 ``7`` 各出现两次,返回 ``-2``; * ``nums = [0, 5, 5]``:唯一值可以是零,返回 ``0``; * ``nums = [9]``:没有重复对,唯一元素本身就是答案。 C++ 实现 -------- .. code-block:: cpp #include #include #include class Solution { private: int sortIntoAdjacentPairs(std::vector nums) { std::sort(nums.begin(), nums.end()); for (int index = 0; index + 1 < static_cast(nums.size()); index += 2) { if (nums[index] != nums[index + 1]) { return nums[index]; } } return nums.back(); } int countOccurrences(const std::vector& nums) { std::unordered_map frequency; for (int value : nums) { ++frequency[value]; } for (const auto& [value, count] : frequency) { if (count == 1) { return value; } } return 0; } int xorAllValues(const std::vector& nums) { int answer = 0; for (int value : nums) { answer ^= value; } return answer; } public: int singleNumber(std::vector& nums) { return xorAllValues(nums); } }; 题解 ---- 先从通用的“找唯一频次”问题出发 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 若没有“其余元素恰好出现两次”这个条件,最直接的办法是为每个值计数,再寻找频次一。哈希表让扫描期望 为 ``O(n)``,但要保存最多 ``O(n)`` 个键,不满足常量空间要求。 另一种办法是排序。相同值会聚到一起,由于数组长度为奇数,可按 ``(0,1)``、``(2,3)`` 等位置检查配对; 第一对不等时,左侧就是唯一值,若此前全部成对则唯一值在末尾。``sortIntoAdjacentPairs`` 不需要哈希表, 却因排序耗费 ``O(n log n)`` 时间,代码还复制了输入以免改变调用者数组。 这两种方法都只利用了“频次不同”,还没有把“重复频次固定为二”转化为运算规则。 为什么异或恰好能消去一对 ~~~~~~~~~~~~~~~~~~~~~~~~ 对固定宽度整数逐位异或,有四个关键性质: .. code-block:: text x ^ x = 0 x ^ 0 = x x ^ y = y ^ x (x ^ y) ^ z = x ^ (y ^ z) 前两条让相同的一对归零,后两条说明归约结果与输入排列、括号顺序无关。因此即使两个相同值在数组中相隔 很远,也可以在证明中把它们重排到一起:所有重复对都变为零,零再被单位元规则删除,最后只剩单次元素。 这相当于只保存每一位出现次数的奇偶性。题目保证除答案外所有完整整数都贡献两次相同比特模式,所以无需 为各个值分别建计数项。 前缀不变量与具体走读 ~~~~~~~~~~~~~~~~~~~~ ``answer`` 在处理任意前缀后,等于该前缀所有元素的异或。读入新值只需再异或一次,不变量继续成立。对 ``[11, -2, 7, 11, 7]``: .. list-table:: :header-rows: 1 * - 已读前缀 - ``answer`` 的符号表达 - 可删除的成对项 * - ``[11]`` - ``11`` - 无 * - ``[11, -2, 7]`` - ``11 ^ -2 ^ 7`` - 无 * - 再读 ``11`` - ``11 ^ 11 ^ -2 ^ 7`` - 两个 ``11`` 归零 * - 再读 ``7`` - ``-2 ^ 7 ^ 7`` - 两个 ``7`` 归零,只剩 ``-2`` 表中重排只用于说明代数等价;代码仍按原数组顺序单次扫描,不需要真的移动元素。 零与负数为何不需要特判 ~~~~~~~~~~~~~~~~~~~~~~ 初值 ``0`` 是异或单位元,不是“尚未找到答案”的哨兵。若唯一值就是零,所有重复对归零后结果仍为零, 语义没有冲突。负数也按其机器整数比特模式逐位参与异或,同一个负数与自身的每一位完全相同,仍满足 ``x ^ x == 0``;这里没有右移或符号扩展,因此无需单独处理符号位。 主解选择与复杂度 ~~~~~~~~~~~~~~~~ 公开入口采用 ``xorAllValues``:一次扫描,时间 ``O(n)``,只维护一个整数,额外空间 ``O(1)``,同时达到 两项进阶要求。哈希计数时间期望 ``O(n)``、空间 ``O(n)``,适合重复次数不固定的通用频次问题;排序方案 时间 ``O(n log n)``。三者的演进说明,真正删除额外状态的是题目“恰好两次”提供的抵消结构。