PAT 1041 Be Unique：找出第一個唯一的彩票號碼

PAT 1041 Be Unique：找出第一個唯一的彩票號碼

PAT（Basic Level）1041 題目模擬火星獨特的彩票規則：從 1 到 10^4 的數字中投注，第一個投注唯一數字者獲勝。給定 N 個投注號碼，需找出第一個只出現一次的數字；若不存在則輸出 "None"。

題目分析

核心任務是統計每個數字的出現次數，並按輸入順序找到第一個計數為 1 的數字。數據範圍：N ≤ 10^5，數字值 ≤ 10^4。此範圍允許使用陣列直接統計頻率，無需雜湊表。

解法：頻率統計 + 順序遍歷

1. 建立大小為 10001 的整型陣列 count 初始化為 0
2. 第一次遍歷輸入數字，統計每個數字出現次數：count[num[i]]++
3. 第二次按原序遍歷數字，找到第一個 count[num[i]] == 1 的數字並輸出
4. 若遍歷結束未找到，輸出 "None"

C語言實現代碼

#include <stdio.h>

int main() {
    int n;
    scanf("%d", &n);
    int num[100000];
    int count[10001] = {0}; // 數字範圍 1~10000

    for(int i = 0; i < n; i++) {
        scanf("%d", &num[i]);
        count[num[i]]++;
    }

    for(int i = 0; i < n; i++) {
        if(count[num[i]] == 1) {
            printf("%d\n", num[i]);
            return 0;
        }
    }
    printf("None\n");
    return 0;
}

關鍵點解析

• 陣列大小：count[10001] 覆蓋 1~10000，下標 0 不用
• 兩次遍歷：第一次統計頻率，第二次按輸入順序查找，保證「第一個」的語義
• 時間複雜度：O(N)，兩次線性遍歷
• 空間複雜度：O(N + 10001) ≈ O(N)，符合限制

樣例驗證

輸入 1：7 5 31 5 88 67 88 17
統計：5→2, 31→1, 88→2, 67→1, 17→1
按序查找：5(2)→31(1) → 輸出 31

輸入 2：5 888 666 666 888 888
統計：888→3, 666→2
無計數為 1 的數字 → 輸出 None

常見誤區

• 直接在統計陣列中按下標順序查找最小的唯一數，而非按輸入順序
• 未處理 "None" 輸出情況
• 陣列大小不足導致越界（需 10001 而非 10000）