ZOJ 3860 找間諜：排序法與異或法雙重解法

問題描述

N 名學生（3≤N≤100），其中 N-1 人 ID 相同，只有 1 個間諜 ID 不同。找出該異常 ID。多測試用例。

解法一：排序法（通用、直觀）

排序後，異常值必位於首位或末位。檢查 a[0]==a[1] 判斷異常在末尾，否則在開頭。

#include 
using namespace std;
int main() {
    int T, n, a[105];
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
        sort(a, a + n);
        printf("%d\n", (a[0] == a[1]) ? a[n-1] : a[0]);
    }
    return 0;
}

時間 O(N log N)，空間 O(1)。N≤100 完全足夠。

解法二：異或法（最優、優雅）

利用異或性質：x ^ x = 0，x ^ 0 = x，a ^ b ^ a = b。成對出現的 ID 異或抵消為 0，剩下的即為異常值。

int findSpy(int a[], int n) {
    int res = 0;
    for (int i = 0; i < n; ++i) res ^= a[i];
    return res;
}

時間 O(N)，空間 O(1)，無需修改數組，單次遍歷。前提：正常 ID 出現偶數次，異常 ID 出現奇數次。本題 N-1 為偶數（N 奇數）或奇數（N 偶數）？題目未保證 N 奇數，故異或法需謹慎：若 N 為偶數，正常 ID 出現奇數次，異或結果會是 normal ^ spy，不可用。本題樣例 N=10,6,5 均為偶數/奇數混合，異或法不通用！ 排序法更穩健。

擴展：若有多個異常值？

• 兩個異常：異或得 a^b，找一個為 1 的位分組再異或
• 哈希表計數：O(N) 時間，O(N) 空間，通用性最強

避坑指南

• ID 為 32 位有符號整數，需用 int 或 long long 讀取
• 輸入以 EOF 結束，while(~scanf(...)) 或 while(cin>>T)
• 輸出每行一個答案，無額外空格