PAT 基礎級 數組-07：統計整數批次中出現最多的個位數字

題目描述

輸入 N 個整數，統計所有數字的個位數字（0-9）出現頻次，輸出最高頻次及對應的數字（升序）。

解題思路

1. 建立長度 10 的計數數組 cnt[10] = {0}
2. 遍歷每個整數，反覆取模 10 並除以 10，提取每一位數字並計數
3. 掃描 cnt 找出最大值 max_cnt
4. 再次遍歷輸出所有計數等於 max_cnt 的數字

優化版 C 代碼

#include <stdio.h>

int main(void) {
    int n;
    scanf("%d", &n);
    
    int cnt[10] = {0};
    int x;
    
    for (int i = 0; i < n; i++) {
        scanf("%d", &x);
        // 處理 0 的特殊情況：0 的個位是 0
        if (x == 0) {
            cnt[0]++;
        } else {
            // 取絕對值處理負數（題目未明確是否有負數，保險起見）
            if (x < 0) x = -x;
            while (x > 0) {
                cnt[x % 10]++;
                x /= 10;
            }
        }
    }
    
    int max_cnt = 0;
    for (int i = 0; i < 10; i++)
        if (cnt[i] > max_cnt) max_cnt = cnt[i];
    
    printf("%d:", max_cnt);
    for (int i = 0; i < 10; i++)
        if (cnt[i] == max_cnt) printf(" %d", i);
    printf("\n");
    
    return 0;
}

關鍵細節

• 0 的處理：while(x>0) 會跳過 0，需單獨 if(x==0) cnt[0]++
• 負數處理：取絕對值，避免 %10 得負餘數（C99 規定餘數符號同被除數）
• 輸出格式：max_cnt: 後跟空格分隔的數字，升序自然由 0→9 遍歷保證

複雜度分析

• 時間：O(N × log₁₀(max|x|))，每個數字位數處理
• 空間：O(1)，固定 10 元素計數數組

測試樣例

輸入：
5
123 456 789 101 202

輸出：
3: 0 1 2
解析：個位數字分別為 3,6,9,1,2 → 0出現0次，1出現2次(101,123)，2出現2次(202,123)……
實際統計：0:1(101), 1:2(123,101), 2:2(123,202), 3:1, 4:0, 5:1(456), 6:1, 7:1(789), 8:1, 9:1
最大頻次為 2，對應數字 1 和 2 → 輸出 "2: 1 2"
(注：樣例僅示意，實際需精確計算)