你如何为一个问题选择正确的数据结构？

Question

你如何为一个问题选择正确的数据结构？

Accepted Answer

选择**最频繁的操作成本最低**的结构，以匹配你的访问模式。首先列出你将执行的操作，估计它们的频率，然后将它们与结构的优势相匹配。

## 决策清单

```text
1. How do you access data?  by index -> array
                            by key   -> hash map
                            by order -> tree / heap
2. Need ordering?           sorted   -> balanced BST / sorted array
                            FIFO     -> queue
                            LIFO     -> stack
3. Frequent middle inserts? -> linked list
4. Need fast "seen it?"     -> set / hash map
5. Need "best/min/max next" -> heap (priority queue)
```

## 将操作与复杂度相匹配

| 需求 | 最佳结构 | 关键操作成本 |
|---|---|---|
| 按索引随机访问 | dynamic array | O(1) |
| 按键查找 | hash map | O(1) avg |
| 排序 + 范围查询 | balanced BST | O(log n) |
| 重复获取最小/最大值 | heap | O(log n) pop |
| FIFO / LIFO | queue / stack | O(1) |
| 前缀搜索 | trie | O(L) |

## 示例推理

```text
"Find the 10 most frequent words in a huge file."
 - count frequencies  -> hash map (O(1) updates)
 - keep top 10        -> min-heap of size 10 (O(log 10) per word)
```

## 为什么这很重要

正确的选择往往是 O(n) 和 O(n²) 解决方案之间的区别——这是对性能影响最大的单一杠杆。

面试官测试的正是这种推理过程：他们想看你如何将需求映射到操作成本，而不是死记硬背各种数据结构。

按索引随机访问	dynamic array	O(1)
按键查找	hash map	O(1) avg
排序 + 范围查询	balanced BST	O(log n)
重复获取最小/最大值	heap	O(log n) pop
FIFO / LIFO	queue / stack	O(1)
前缀搜索	trie	O(L)