algorithm - 从二维排序数组中找到第 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)) 来执行，我们将得到答案，导致我上面的估计。