实现按 key 有序、可复用删除位置的 put
哪些公司问过
答案要点
- 先澄清题意:有序存储、覆盖与插入、delete 的语义
- 二分查找定位 key 或插入点,墓碑保留 key 以维持有序
- 删除只做标记,插入时若相邻位置是墓碑且不破坏有序则复用
- 墓碑比例过高时整体压缩,避免空间与查找退化
- 复杂度:查找 O(log n),复用插入 O(1),搬移插入 O(n);替代方案为平衡树
易错点
- 删除时直接搬移数组,没有体现复用位置的要求
- 复用墓碑时没检查有序性,破坏后续二分查找
- 墓碑只增不减,长期运行后空间和查找性能下降
面试官常见追问
- 为什么墓碑要保留原 key?
- 什么场景会用到这种墓碑设计?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。