java - 在二维数组上查找第 K 个最小元素（或中值）的最快算法？

我看到很多关于相关主题的 SO 主题，但没有一个提供有效的方法。

我想k-th在 2D 数组中找到最小元素（或中位数），[1..M][1..N]其中每一行按升序排序，并且所有元素都是不同的。

我认为有O(M log MN)解决方案，但我不知道如何实施。（中位数的中位数或使用具有线性复杂性的分区是一些方法，但现在不知道了......）。

这是一个古老的谷歌面试问题，可以在这里搜索。

但现在我想要提示或描述最有效的算法（最快的算法）。

我也在这里读过一篇论文，但我不明白。

更新 1：在这里找到了一个解决方案，但是当维度是奇数时。

标签： javapythonarraysalgorithmdata-structures

添加了另一个答案以提供实际的解决方案。由于评论中有相当大的兔子洞，所以留下了这个。

我相信最快的解决方案是 k-way 合并算法。它是一种将排序列表与项目总数O(N log K)合并为一个大小为的排序列表的算法。KNN

给定一个MxN清单。这最终成为O(MNlog(M)). 但是，这是为了对整个列表进行排序。由于您只需要第一个K最小的项目而不是全部N*M，因此性能是O(Klog(M)). 这比你正在寻找的要好得多，假设O(K) <= O(M).

虽然这假设您已经N对 size 列表进行了排序M。如果您实际上已经M对 size 列表进行了排序N，那么这可以通过更改循环数据的方式轻松处理（请参见下面的伪代码），尽管这确实意味着性能是O(K log(N))相反的。

k-way 合并只是将每个列表的第一项添加到具有O(log N)插入和O(log N)查找思维的堆或其他数据结构中。

k-way 合并的伪代码看起来有点像这样：

对于每个排序列表，将第一个值插入数据结构中，并通过某种方式确定该值来自哪个列表。IE：您可能会插入[value, row_index, col_index]数据结构，而不仅仅是value. 这也使您可以轻松地处理对列或行的循环。
从数据结构中删除最小值并附加到排序列表。
鉴于步骤＃2中的项目来自列表，I将列表中的下一个最小值添加I到数据结构中。IE：如果值是row 5 col 4 (data[5][4]). 然后，如果您将行用作列表，则下一个值将是row 5 col 5 (data[5][5]). 如果您使用列，则下一个值为row 6 col 4 (data[6][4]). 像 #1 一样将下一个值插入到数据结构中（即[value, row_index, col_index]：）
根据需要返回步骤 2。

根据您的需要，执行步骤 2-4K次。