面试题库 › 算法 / 大模型 › 每行有序的矩阵中第 K 小的元素(堆解法)

每行有序的矩阵中第 K 小的元素(堆解法)

难度 ★★☆在 1 场真实面经中被问到 方向:算法 / 大模型考点:TopK与海量数据

哪些公司问过

快手1

常见岗位:推理部署与加速

答案要点

  1. 多路归并:每行当作有序序列,第 k 次弹出的就是第 k 小
  2. 小顶堆初始放入每行首元素及其行列下标,C++ 需用 greater 构造小顶堆
  3. 弹出堆顶后把同一行的下一个元素入堆,重复 k 次
  4. 时间 O(n + k log n),空间 O(n);k 小于行数时只放前 k 行
  5. 行列都有序时可用值域二分,从左下角计数,O(n log(max−min))

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题