問題描述
生成 N 個範圍內的隨機整數，去重後升序輸出。
1164：N ≤ 10^8, 值域 [0, 910305]
1287：N ≤ 5×10^6, 值域 [0, 10^9]
1164：直接定址法（位圖/布爾數組）
值域上限 910305 < 10^6，可直接開布爾數組 `bool num[910306]`。
讀入即標記 `num[x]=true`，統計 true 個數，順序遍歷輸出。
時間 O(N + M)，空間 O(M)，M=910306，極快極省。
1287：值域過大，需哈希去重 + 排序
值域 10^9 無法直接定址。N=5×10^6，可用哈希表去重。
方案一：排序去重（簡單有效）
sort(a, a+n);
int cnt = 1;
for (i=1; i
時間 O(N log N)，空間 O(N)，500萬整數排序約 1-2 秒，可行。
方案二：拉鏈法哈希表（手寫高性能）
- 取模基數 `MP = 1007`（質數）
- 節點池 `Node nd[MP]` 預分配，避免動態分配開銷
- 頭指針數組 `Node* pnd[MP+1]`
- 插入時計算哈希，遍歷鏈表檢查重複，無則頭插法加入
- 同時記錄不重複值到數組 `a[]`，最後排序輸出
struct Node { int d; Node* next; };
Node* pnd[MP+1]; Node nd[MP+1]; int n_cnt=0, a_cnt=0;
while (n--) {
scanf("%d", &d);
int p = d % MP;
Node* pt = pnd[p];
bool found = false;
while (pt) { if (pt->d == d) { found=1; break; } pt = pt->next; }
if (!found) {
nd[n_cnt].d = d;
nd[n_cnt].next = pnd[p];
pnd[p] = &nd[n_cnt++];
a[a_cnt++] = d;
}
}
sort(a, a+a_cnt);
關鍵優化點
- 節點池預分配：避免 `new` 開銷，內存連續，缓存友好
- 指針而非索引：直接操作指針，消除數組下標轉換
- 質數取模：減少哈希衝突
- 同步記錄去重值：避免二次遍歷哈希表收集
複雜度對比
| 方法 | 時間 | 空間 | 備註 |
|---|
| 定址法(1164) | O(N+M) | O(M) | M=910306，最優 |
| 排序去重 | O(N log N) | O(N) | 通用，常數大 |
| 拉鏈法哈希 | O(N) 期望 | O(N) | 手寫高性能，適合大值域 |
總結
兩題展示了根據值域大小選擇去重策略的決策邏輯：
- 值域小 (≤ 10^7)：直接定址法/位圖，O(N) 時間，空間換時間
- 值域大、數據量中等：排序去重，代碼簡單，O(N log N) 可接受
- 值域大、數據量大、追求極致性能：手寫拉鏈法哈希 + 節點池，O(N) 期望時間
哈希表實現中，節點池預分配、指針操作、質數取模是高性能關鍵。
