只出现一次的数字 | 秋招知识库

利用异或运算 $a \oplus a = 0$ 的性质，我们可以用异或来「消除」所有出现了两次的元素，最后剩下的一定是只出现一次的元素。

例如 $nums = [4, 1, 2, 1, 2]$ ，把所有元素异或：

\begin{aligned} 4 \oplus 1 \oplus 2 \oplus 1 \oplus 2 \\ = & 4 \oplus (1 \oplus 1) \oplus (2 \oplus 2) \\ = & 4 \oplus 0 \oplus 0 \\ = & 4 \end{aligned}

其中用到了异或运算的交换律 $a \oplus b = b \oplus a$ ，以及结合律 $(a \oplus b) \oplus c = a \oplus (b \oplus c)$ （类比加法）。

代码中，初始化 $ans = 0$ 是因为 $0 \oplus a = a$ ，相当于我们从第一个数开始，和其他数异或。

Python 解法1C++ 解法1

python

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        return reduce(xor, nums)

cpp

// C++ 版待补充

C++ 解法2

cpp

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

复杂度分析

时间复杂度： $O (n)$ ，其中 $n$ 为 $nums$ 的长度。
空间复杂度： $O (1)$ 。

相似题目

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

复杂度分析 ​

相似题目 ​

分类题单 ​

复杂度分析

相似题目

分类题单