0260. Single Number III ======================= 题目信息 -------- :题号: 0260 :难度: Medium :主题: 数组、位运算、异或、分组 :原题: `LeetCode 0260 `_ :重点: 恰有两个不同值只出现一次、其他值都出现两次、返回顺序不限、线性时间与常数额外空间 题目重述 -------- 给定整数数组 ``nums``,其中恰好有两个不同的元素各出现一次,其余每个元素都恰好出现两次。返回这两个只出现一次的元素。 数组长度位于 ``[2, 3 * 10^4]``,元素值位于 32 位有符号整数范围 ``[-2^31, 2^31 - 1]``。两个答案可以按任意顺序返回。题目要求整体时间复杂度为 ``O(n)``,并且除返回结果外只使用常数级额外空间;函数不需要改变输入数组。 自建示例 -------- 唯一值位于数组中间和末尾: .. code-block:: text 输入:nums = [4, 1, 4, 6, 1, 9] 输出:[6, 9] 解释:4 和 1 都各出现两次,只有 6 和 9 各出现一次;返回 [9, 6] 也合法。 包含负数与零: .. code-block:: text 输入:nums = [-7, 0, 5, -7, 8, 5] 输出:[0, 8] 解释:-7 和 5 成对出现,剩余的 0 与 8 就是两个唯一元素。 先得到两个答案的异或 -------------------- 把所有元素异或在一起。每个成对出现的值会因为 ``x ^ x = 0`` 抵消,最后得到: .. code-block:: text mixed = unique_a ^ unique_b 两个唯一值不同,所以 ``mixed`` 至少有一个置位。取 ``mixed`` 的最低置位 ``bit``, 则两个唯一值在这一位上必然一个为 0、一个为 1。按这一位把原数组分成两组:每组中的成对元素仍在同组抵消, 两个唯一值则分别落在不同组,各组异或结果就是两个答案。 取最低置位时使用无符号位模式,避免唯一值或异或结果恰好包含有符号 ``int`` 的最高位时对 ``-INT_MIN`` 做有符号溢出运算。 正确性说明 ---------- ``mixed`` 的每个二进制位表示两个唯一值是否在该位不同。选中的 ``bit`` 能把它们分开; 任一重复值与自身的位模式相同,因此一定进入同一组并抵消。两个分组的异或结果只剩各自的唯一值, 返回顺序不影响题目合同。 C++ 实现 -------- .. code-block:: cpp #include class Solution { public: std::vector singleNumber(std::vector& nums) { std::uint32_t mixed = 0; for (int value : nums) { mixed ^= static_cast(value); } const std::uint32_t bit = mixed & (~mixed + 1u); std::uint32_t first = 0; std::uint32_t second = 0; for (int value : nums) { const std::uint32_t bits = static_cast(value); if ((bits & bit) != 0) first ^= bits; else second ^= bits; } return { static_cast(first), static_cast(second) }; } }; 代码分析 -------- 两次扫描,每个元素只做常数次异或和判断,时间复杂度为 ``O(n)``;只保存三个无符号位状态, 除返回数组外额外空间为 ``O(1)``。``std::uint32_t`` 表达题目 32 位整数的位模式, 不需要排序、哈希表或修改输入数组。