解题思路

这道题可以用异或运算（符号 ^）来解，非常巧妙。

异或有两个重要性质：

1. 相同为 0：a ^ a == 0，一个数和自己异或结果是 0；
2. 和 0 异或不变：a ^ 0 == a。

所以，把读到的所有数一个个异或起来，成对出现的相同数会互相抵消变成 0，最后剩下的，就是那个没有配成对的数——也就是答案。

例如：3 3 5 5 7，先算 3^3=0，再算 0^5^5=0，最后 0^7=7，相同的 3 和 5 都抵消掉了，剩下的 7 就是只出现一次的那个数。

参考代码

// P4484 只出现一次的整数：利用异或运算，成对出现的数互相抵消，剩下答案
#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);   // 加快读写，应对最多10^6个数
    cin.tie(0);
    int n;
    cin >> n;
    int ans = 0;
    // 异或性质：a^a=0，a^0=a，即相同的数会抵消
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        ans ^= x;   // 把所有数做异或，最终剩下的就是答案
    }
    cout << ans << endl;
    return 0;
}

复杂度分析

只需要从头到尾把每个数异或一次，时间复杂度 O(n)，而且不需要开数组，额外空间只有 O(1)，特别适合 n 最大到 10⁶ 的情况。