实现支持按索引访问的有序 map
哪些公司问过
答案要点
- 先确认顺序语义:插入顺序还是键排序
- 插入顺序:哈希表 + 动态数组,查找与按索引访问 O(1)
- 删除可用标记加定期压缩,或接受 O(n) 搬移
- 键排序:顺序统计树(节点维护子树大小),各操作 O(log n)
- 空间 O(n),修改时同步维护下标映射或子树大小
易错点
- 删除后没有更新哈希表中其他元素的下标
- 旋转或插入删除后忘记维护子树大小
- 没区分插入顺序和键顺序,方案与需求不符
面试官常见追问
- 顺序统计树怎么找第 k 个元素?
- 有没有现成的标准库可用?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。