ZeroJudge 解題筆記：e836. P3. 數字統計 (Counting)

作者：王一哲
日期：2025年2月9日



ZeroJudge 題目連結：e836. P3. 數字統計 (Counting)

解題想法

這題用字典計數比較方便。

Python 程式碼

可以使用 collections 函式庫的 Counter，這是專門用來計算數量的工具，輸入一個可以迭代的物件，回傳物件中各項資料的數量。使用時間約為 45 ms，記憶體約為 3.8 MB，通過測試。

import sys
from collections import Counter

for line in sys.stdin:
    n = int(line)  # n 個數字
    rs = list(map(int, input().split()))  # 讀取一行數字
    cnt = Counter(rs)  # 計數器
    print(len(cnt))  # 印出不同的數字數量
    imax = max(cnt.values())  # 相同數字最大數量
    if imax < 2: print("NO")  # 沒有重複的數字，印出 NO
    else:  # 否則依照出現順序印出數字
        tmp = []  # 暫存用的串列
        for r in rs:  # 依序由 rs 讀取數字 r
            if cnt[r] == imax and r not in tmp:  # 如果 r 的數量最多而且不在 tmp 之中
                tmp.append(r)  # r 加入 tmp
        print(*tmp)  # 印出 tmp

由於 Counter 的 key 值會依照輸入的物件資料順序排序，上方程式第 11 到 16 行可以改為以下這行，使用時間約為 37 ms，記憶體約為 3.8 MB，通過測試。

else: print(*[key for key, val in cnt.items() if val == imax])

也可以用預設的字典格式儲存各個數字的數量，但是要記得先檢查字典之中是否有這個 key 值。使用時間約為 19 ms，記憶體約為 3.5 MB，通過測試。

import sys

for line in sys.stdin:
    n = int(line)  # n 個數字
    rs = list(map(int, input().split()))  # 讀取一行數字
    cnt = dict()  # 計數器
    imax = 0  # 相同數字最大數
    for r in rs:  # 依序由 rs 讀取數字 r
        if r not in cnt: cnt[r] = 1  # 如果 r 不在 cnt 之中，cnt[r] 設為 1
        else: cnt[r] += 1  # 否則，cnt[r] 加 1
        imax = max(imax, cnt[r])  # 更新 imax
    print(len(cnt))  # 印出不同的數字數量
    if imax < 2: print("NO")  # 沒有重複的數字，印出 NO
    else: print(*[key for key, val in cnt.items() if val == imax]) # 否則依照出現順序印出數字

C++ 程式碼

使用時間約為 3 ms，記憶體約為 384 kB，通過測試。

#include <iostream>
#include <vector>
#include <map>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n;  // n 個數字
    while(cin >> n) {
        vector<int> rs (n);  // 數字
        map<int, int> cnt;  // 計數器
        int imax = 0;  // 相同數字最大數量
        for(int i=0; i<n; i++) {  // 讀取 n 個數字
            int r; cin >> r;
            rs[i] = r;  // 更新 rs
            cnt[r]++;  // 更新 cnt
            if (cnt[r] > imax) imax = cnt[r];  // 如果 r 對應的數量大於 imax，更新 imax
        }
        cout << cnt.size() << "\n";  // 印出不同的數字數量
        if (imax < 2) {  // 沒有重複的數字，印出 NO
            cout << "NO\n";
        } else {  // 否則依照出現順序印出數字
            vector<int> tmp;  // 暫存用的陣列
            map<int, bool> found;  // 每個數字是否已加入 tmp
            for(int r : rs) {  // 依序由 rs 讀取數字 r
                if (cnt[r] == imax && !found[r]) {  // 如果 r 的數量最多而且不在 tmp 之中
                    tmp.push_back(r);  // r 加入 tmp
                    found[r] = true;
                }
            }
            for(int i=0; i<(int)tmp.size(); i++) {  // 印出 tmp
                cout << tmp[i] << " \n"[i == (int)tmp.size()-1];
            }
        }
    }
    return 0;
}