从2-d排序的数组中找到第k个最大元素

Question

我有一个二维数组.行和列已排序.如何从二维数组中找到第k个最大元素？

Answer 1

如果你有一个n * n矩阵,那么平均时间就可以这样做O(n * log(n) * log(n)).

你要做的是将矩阵分解为一系列排序的数组,然后立即对所有这些数组进行二进制搜索.例如,假设n = 4和从中索引(0,0)到(3,3).我们可以将其分解为从列向上升到对角线的数组,然后向右转以完成行.这将为我们提供以下一组排序数组:

1. (0,0), (0,1), (0,2), (0,3), (1,3), (2,3), (3,3)
2. (1,0), (1,1), (1,2), (2,2), (3,2)
3. (2,0), (2,1), (3,1)
4. (3,0)

这为我们n提供了矩阵中的排序列表.

所以我们需要弄清楚k第一个元素在一组排序数组中的位置.

我们将通过二进制搜索来实现它的值.

从获取最长数组的中点开始,这将是(0,3)示例中的元素.然后对于每个其他数组计算出多少大于,小于或等于该值.(你可以通过二分搜索找到它.)这让我们弄清楚k第一个元素在哪一边划分.如果它与我们刚刚选择的元素匹配,我们就有了答案.否则我们可以扔掉每个阵列的平均一半(有时扔掉整个阵列)并重复.

在进行平均O(log(n))操作后O(n log(n)),我们将得到答案,从而达到我的估算.

Answer 2

跨最小维度进行 n 路合并。当你完成第 k 个项目时，你就完成了。

测试显示此操作以 k lg d 运行，其中 d = min(rows,cols)。