LeetCode Hot 100 | 96. 只出现一次的数字

LeetCode 136. 只出现一次的数字 (Single Number)

1. 核心思路：异或运算的性质

本题最优雅的解法是利用 异或运算 (XOR) 的数学性质。

异或运算 ^ 有以下三个关键特性：

• 归零律：任何数与自身异或结果为 0，a ^ a = 0
• 恒等律：任何数与 0 异或结果为本身，a ^ 0 = a
• 交换律与结合律：异或运算满足交换律和结合律，运算顺序不影响结果

算法推导：

题目说明「除某个元素仅出现 1 次外，其余每个元素都出现 2 次」。

假设数组为 [a, b, c, b, a]，其中 c 是只出现一次的元素：

a ^ b ^ c ^ b ^ a
= (a ^ a) ^ (b ^ b) ^ c    // 利用交换律和结合律，将相同元素配对
= 0 ^ 0 ^ c                 // 利用归零律
= c                         // 利用恒等律

因此，将数组中所有元素进行异或运算，成对出现的元素会相互抵消为 0，最终留下的就是只出现一次的那个数字。

2. 代码实现

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ret = 0;
        // 利用异或的性质：成对出现的数字会相互抵消
        for (const int& num : nums) {
            ret ^= num;
        }
        return ret;
    }
};

3. 关键细节备忘 (Key Takeaways)

1. 异或运算的妙用：

   • 当题目出现「一个数出现 1 次，其他出现 2 次」的模式时，优先考虑异或解法。
   • 这是位运算的经典应用场景，时间复杂度 O(N)，空间复杂度 O(1)，无法更优。

2. 初始化值的选择：

   • 将 ret 初始化为 0 是安全的，因为 0 ^ x = x，不会影响最终结果。

3. 复杂度分析：

   • 时间复杂度：$O(N)$ — 只需遍历数组一次
   • 空间复杂度：$O(1)$ — 只使用常数额外空间