Sicily 2005：Lovely Number - 找出現奇數次的數字

問題描述

給定 t 個整數，其中只有一個數字出現奇數次，其餘均出現偶數次。輸出該數字。

解法：排序 + 相鄰抵消

1. 讀入數組並排序。
2. 遍歷數組，若 a[i] == a[i+1]，說明這對出現偶數次，將兩者置 0（或跳過），i += 2。
3. 最後剩下非 0 的元素即為答案。

參考代碼 (C++)

#include 
#include 
using namespace std;

int main() {
    int t;
    while (cin >> t) {
        int *a = new int[t];
        for (int i = 0; i < t; ++i) cin >> a[i];
        sort(a, a + t);
        for (int i = 0; i < t - 1; ++i) {
            if (a[i] == a[i+1]) {
                a[i] = a[i+1] = 0;
                ++i; // 跳過下一個
            }
        }
        for (int i = 0; i < t; ++i)
            if (a[i] != 0) { cout << a[i] << endl; break; }
        delete[] a;
    }
    return 0;
}

更優解法：異或運算 O(n) 時間 O(1) 空間

利用 x ^ x = 0, x ^ 0 = x，所有數異或一遍，結果即為出現奇數次的數。無需排序，無需額外空間。

int ans = 0;
for (int i = 0; i < t; ++i) {
    int x; cin >> x;
    ans ^= x;
}
cout << ans << endl;

複雜度對比

推薦異或解法，簡潔高效。