数据结构选型速记

数据结构选型速记

一、面试常考点

1. 选型原则

先看操作类型（查找/插入/删除/区间），再看数据规模和是否有序。（深入阅读：复杂度分析与方案选型）

2. 高频映射

• 判重、频次统计：哈希表。（深入阅读：哈希表频次统计）
• 区间查询：前缀和/树状数组/线段树。（深入阅读：一维前缀和区间查询）
• TopK：堆。（深入阅读：TopK 小顶堆）
• 最短路径（无权）：BFS。（深入阅读：BFS 最短路径）

二、速记表

场景	优先结构	说明
高频查找	哈希表	平均 O(1)，注意哈希冲突
有序查找	二分 + 有序数组	查询 O(log n)，插入成本高
动态最值	堆	取最值 O(1)，更新 O(log n)
队头队尾操作	双端队列	滑动窗口高频使用