algorithm - 如何从 mxn 阶的排序矩阵中找到第 N 个最大值

Question

具有 n 行和 m 列的整数矩阵，并且行和列的元素都按非递减顺序排序。找到数组第 N 个最大值的最佳方法是什么？例如，如果给定的矩阵是 4x5

1  4  5  7
2  6  8  9
10 14 19 23
12 23 33 60
15 24 35 72

从矩阵中找到第 3 个最大值，即 35。

Answer 1

我们的目标是检查最少的元素以找到第 N 个最大值。所以我们按照以下顺序从右下角开始检查元素:{72}, {35, 60}, {24, 33, 23}, {15, 23, 19, 9}, {12, 14, 8, 7} ...，直到我们找到第 N 个最大值。

因为我们知道任何元素都大于或等于它的上元素和左元素(如果它们存在的话)，按照这个顺序搜索可以确保我们找到正确的答案。但是我们必须完整地搜索每个子集，因为每个子集内的元素可能未排序。

正确的解决方案涉及最大堆。我们从右下角的元素开始，将两个相邻的元素添加到堆中。每次我们从堆中提取最大元素并将新的相邻(左，顶)元素添加到堆中。这样，我们实际上是对矩阵进行排序，找到第 N 个元素。