排序矩阵中的第K个最小元素
Mic*_*ael 19 arrays algorithm matrix multidimensional-array data-structures
这是一个面试问题.
找到具有已排序行和列的矩阵中的第 K 个最小元素.
它是正确的,K个次 最小的元素之一,a[i, j]如i + j = K？
nne*_*neo 36
假.
考虑一个像这样的简单矩阵:
1 3 5
2 4 6
7 8 9
9是最大(第9个最小)元素.但是9是在A [3,3]和3 + 3!= 9.(无论你使用什么索引约定,它都不是真的).
您可以在O(k log n)时间内通过逐步合并行来解决此问题,使用堆扩充以有效地找到最小元素.
基本上,您将第一列的元素放入堆中并跟踪它们来自的行.在每一步中,从堆中删除最小元素并从它来自的行中推送下一个元素(如果到达行的末尾,则不要推送任何内容).删除最小值和添加新元素都需要花费O(log n).在第j步中,删除j最小的元素,因此在k完成操作的总成本后,您将完成O(k log n) 操作(其中n是矩阵中的行数).
对于上面的矩阵,您最初从1,2,7堆开始.你删除1并添加3(因为第一行1 3 5)得到2,3,7.你删除2并添加4以获取3,4,7.删除3并添加5以获取4,5,7.删除4并添加6以获取5,6,7.请注意,我们将按全局排序顺序删除元素.您可以看到,继续此过程将k在k次迭代后产生最小的元素.
(如果矩阵的行数多于列数,则对列进行操作以减少运行时间.)
- 如果只对行或列进行排序,则此解决方案最有效(实质上,它在外部排序中是n路合并).@ user1987143是更好的,因为它利用了行和列都被排序的事实. (2认同)
- 您已将行数定义为n，那么如果您用第一列初始化最小堆，则运行时不是n + k log（n）吗？（您似乎没有在运行时计算中考虑该初始化步骤）。 (2认同)
小智 25
O(k log(k)) 解.
建立一个minheap.
添加
(0,0)到堆中.虽然,我们没有找到kth最小的元素,(x,y)从堆中删除顶部元素并添加下两个元素[(x+1,y),(x,y+1)]如果它们之前没有被访问过.
我们正在进行O(k)一堆大小的操作O(k),因此也就是复杂性.
小智 7
这个问题可以使用二分搜索和排序矩阵中的优化计数来解决。二分搜索需要O(log(n))时间，对于每个搜索值，平均需要n次迭代才能找到小于搜索数字的数字。二分搜索的搜索空间被限制为矩阵中的最小值mat[0][0]和最大值mat[n-1][n-1]。
对于从二进制搜索中选择的每个数字，我们需要计算小于或等于该特定数字的数字。因此 可以找到最小的数字。
为了更好的理解你可以参考这个视频：
https://www.youtube.com/watch?v=G5wLN4UweAM&t=145s