跳到主要内容

LeetCode 136. 只出现一次的数字

本节目标

利用异或的成对消去性质，在一次遍历中找出唯一未配对的数。

这道题承接二进制与位运算基础：当除一个数外的所有数都恰好出现两次时，异或能让每一对相同数消去。

查看原题

题意与约束​

给定一个非空整数数组 nums，除一个元素只出现一次外，其余每个元素都恰好出现两次。返回只出现一次的元素。

  • 1 <= nums.length <= 3 * 10^4
  • 每个 nums[i] 都在 -3 * 10^4 到 3 * 10^4 之间。
  • 题目保证答案唯一。

从成对消去想到异或​

令 answer 从 0 开始，依次与数组中的数异或。异或满足 a ^ a = 0，且 a ^ 0 = a：每个出现两次的数都会消去，只出现一次的数最终留下来。

哈希集合也能记录每个数是否出现过，但需要 O(n) 额外空间；这里直接利用题目的“恰好两次”约束，把额外空间降到 O(1)。

顺序为什么不重要​

异或满足交换律 a ^ b = b ^ a 和结合律，因此可以不考虑数组中两次出现的位置，把相同的数重新配对。一次从左到右的累计计算，等价于先让所有成对元素消去，再保留唯一元素。

例如 [4, 1, 2, 1, 2] 的结果为 4 ^ (1 ^ 1) ^ (2 ^ 2) = 4。

代码实现​

两份源码都只维护 answer，每读到一个数就执行一次异或。

C++17
#include <vector>
using namespace std;

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int answer = 0;
        for (int num : nums) {
            answer ^= num;
        }
        return answer;
    }
};

复杂度分析​

  • 时间复杂度：遍历数组一次，为 O(n)。
  • 额外空间复杂度：只使用 answer，为 O(1)。

易错点​

  • 用加减法抵消：整数溢出和重复次数变化都会破坏这种推理；本题应使用异或。
  • 忘记初始值：累计值必须从 0 开始，因为 a ^ 0 = a。
  • 将哈希集合当作唯一解法：它能通过，但没有利用“其他元素恰好两次”的约束，也多用了 O(n) 空间。
  • 套用到出现三次或多个未配对数的题：此时成对消去不再成立，需要按位统计或拆分分组。

模式迁移​

遇到“多数值成偶数次出现，少数值需保留”的题，先确认异或后哪些值会消去、最后会留下几个值。若恰好只有一个未配对数，就可直接累计异或；若有两个未配对数，可继续利用最高有效位把数分组。