解题思路

题目给了 n 个整数，其中只有一个数出现了奇数次，其余的数都出现了偶数次，要找出那个出现奇数次的数。

有一个非常巧妙的工具：按位异或（^）。它有两个性质：

1. 一个数和它自己异或，结果等于 0：x ^ x = 0。
2. 异或满足交换律和结合律，先算哪两个都行。

把题目里所有数从头到尾异或一遍：

• 出现偶数次的数，会和自己配对变成 0；
• 两个 0 继续异或还是 0；
• 最后剩下的，就是那个出现奇数次的数。

比如样例：3 3 1 2 4 2 5 5 4，异或一遍： 3^3=0，0^1=1，1^2=3，3^4=7，7^2=5，5^5=0，0^4=4，4^5=1，结果就是 1，正好是出现奇数次的那个数。

参考代码

// 用途：n个整数中恰有1个数出现奇数次，其余出现偶数次，找出那个数
// 技巧：异或运算满足交换律，成对出现的数异或后为0，结果就是答案
#include <iostream>
using namespace std;
int main() {
    int n, x, ans = 0;
    cin >> n;                       // 读入整数个数
    for (int i = 0; i < n; i++) {
        cin >> x;                   // 依次读入每个整数
        ans = ans ^ x;              // 累异或
    }
    cout << ans;                    // 输出出现奇数次的数
    return 0;
}

复杂度分析

只需要一次循环把 n 个数都异或一遍，时间复杂度是 O(n)，空间复杂度是 O(1)。n 最大 5000，跑得飞快。