每行有序的矩阵中第 K 小的元素(堆解法)
哪些公司问过
答案要点
- 多路归并:每行当作有序序列,第 k 次弹出的就是第 k 小
- 小顶堆初始放入每行首元素及其行列下标,C++ 需用 greater 构造小顶堆
- 弹出堆顶后把同一行的下一个元素入堆,重复 k 次
- 时间 O(n + k log n),空间 O(n);k 小于行数时只放前 k 行
- 行列都有序时可用值域二分,从左下角计数,O(n log(max−min))
易错点
- 直接用默认的 priority_queue,得到的是大顶堆
- 把所有元素都放进堆,复杂度退化为 O(n² log n)
- 弹出后没判断所在行是否还有下一个元素,导致越界
面试官常见追问
- 值域二分的计数怎么做?
- priority_queue 怎么存三元组并按值排序?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。