题目

解法：异或运算

思路

利用异或运算的自反性（a^a=0）和恒等性（a^0=a）特性，将所有元素异或后成对元素抵消，剩余即为唯一元素。

该方法正确的原因是异或运算满足交换律和结合律。设数组为{a1,a1,a2,a2,…,an,an,x}，则异或结果为(a1^a1)^(a2^a2)^…^(an^an)^x = 0^0^…^0^x = x。无论元素顺序如何，该数学性质保证结果必然是唯一元素。

• Step 1: 初始化 ans = 0
• Step 2: 遍历数组，执行 ans ^= nums[i]
• Step 3: 返回 ans

复杂度

• 时间复杂度: $O(n)$
• 空间复杂度: $O(1)$

代码

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for(int i = 0;i<nums.size();i++){
            ans ^= nums[i];
        }
        return ans;
    }
};