多路有序结果归并去重并取Top-K
哪些公司问过
58同城1
答案要点
- 用大小为m的堆做多路归并,堆元素记录值、路号和路内下标
- 弹出堆顶后补入同一路的下一个元素,凑满k个即停止,不必合并全部数据
- 按值去重时重复项在输出序列中相邻,和上一个输出比较即可;按ID去重用哈希集合
- 时间O(m + (k+d)·log m),空间O(m+k);只有两路时直接双指针归并即可
易错点
- 把所有路先合并再整体排序,复杂度O(N log N),没利用已有序的性质
- 弹出元素后忘了补入同一路的下一个元素,或该路取完时下标越界
- 按ID去重却只和上一个元素比较,漏掉不相邻的重复
- 堆的比较方向和排序方向不一致,取成了最小的k个
面试官常见追问
- 各路分数尺度不一致怎么合并?
- 如果每一路数据量极大、存在磁盘上呢?
- 如果各路并不有序呢?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。