NOJ 1601 數字統計：哈希表優化計數排序輸出

NOJ 1601「數次統計」：n 個自然數 (≤1.5×10⁹)，不超過 10000 種不同值。統計每值出現次數，按值升序輸出。本文解析開放地址法哈希表實現 O(n) 統計，避免 O(n²) 線性查找。

問題分析

• n 可大（題目暗示），但不同值 ≤ 10000。
• 值範圍大 (1.5×10⁹)，不能直接開數組索引。
• 需按值排序輸出 → 統計後需提取所有鍵值對排序。

哈希表設計：開放地址法

• 表大小：取略大於 10000 的質數，如 10009 或 10007。
• 哈希函數：h(x) = x % MOD。
• 衝突解決：線性探測 (h(x) + i) % MOD。
• 節點結構：{int key, cnt;}，key = -1 表示空槽。

插入/統計邏輯

struct Node { int key, cnt; } hashTable[10010];

void init() {
    for (int i = 0; i < MOD; ++i) hashTable[i].key = -1;
}

void insert(int x) {
    int pos = x % MOD;
    while (true) {
        if (hashTable[pos].key == x) { // 找到
            hashTable[pos].cnt++;
            return;
        }
        if (hashTable[pos].key == -1) { // 空槽
            hashTable[pos].key = x;
            hashTable[pos].cnt = 1;
            return;
        }
        pos = (pos + 1) % MOD; // 線性探測
    }
}

統計後排序輸出

1. 遍歷哈希表，將所有 key != -1 的節點複製到數組。
2. 按 key 升序排序（qsort 或 sort）。
3. 依次輸出 key cnt。

完整代碼（C++）

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MOD = 10009;
const int MAXN = 10020;

struct Node { int key, cnt; } ht[MAXN], tmp[MAXN];

bool cmp(Node a, Node b) { return a.key < b.key; }

int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        // 初始化
        for (int i = 0; i < MOD; ++i) ht[i].key = -1, ht[i].cnt = 0;

        // 統計
        for (int i = 0; i < n; ++i) {
            int x; scanf("%d", &x);
            int pos = x % MOD;
            while (true) {
                if (ht[pos].key == x) { ht[pos].cnt++; break; }
                if (ht[pos].key == -1) { ht[pos].key = x; ht[pos].cnt = 1; break; }
                pos = (pos + 1) % MOD;
            }
        }

        // 收集並排序
        int m = 0;
        for (int i = 0; i < MOD; ++i)
            if (ht[i].key != -1) tmp[m++] = ht[i];
        sort(tmp, tmp + m, cmp);

        // 輸出
        for (int i = 0; i < m; ++i)
            printf("%d %d\n", tmp[i].key, tmp[i].cnt);
    }
    return 0;
}

複雜度分析

• 哈希操作：期望 O(1)，最壞 O(表大小) 但負載因子 < 1 時極快。
• 總統計：O(n) 期望。
• 排序：O(m log m)，m ≤ 10000。
• 空間：O(MOD) ≈ 10000 節點。

關鍵細節

1. 質數模數：減少衝突，10009 是常用質數。
2. 線性探測：簡單高效，負載因子 < 0.7 時性能好。
3. 多測試用例：每用例完全重置哈希表。
4. 輸入結束：scanf != EOF。

總結

本題展示了「大數值範圍 + 少量不同值 + 需排序輸出」的標準解法：哈希表統計 + 提取排序。開放地址法代碼簡短、無指針開銷、緩存友好，是競賽編程中實現哈希表的首選。若語言支持（C++ unordered_map, Java HashMap），直接用標準庫更簡潔；但理解底層實現有助於處理特殊約束（如內存限制、自定義哈希）。