具有 n 行和 m 列的整数矩阵以及行和列的元素都按非递减顺序排序。找到数组的第 N 个最大值的最佳方法是什么？例如，如果给定的矩阵是 4x5
1 4 5 7
2 6 8 9
10 14 19 23
12 23 33 60
15 24 35 72
从矩阵中找到第三个最大值，即 35。
user2803850
问问题
352 次
2 回答
2
我们的目标是检查最少的元素以找到第 N 个最大值。所以我们从右下角开始依次检查元素：{72}, {35, 60}, {24, 33, 23}, {15, 23, 19, 9}, {12, 14, 8, 7} ...，直到我们找到第 N 个最大值。
因为我们知道任何元素都大于或等于它的上和左元素（如果它们存在），所以按这个顺序搜索可以确保我们找到正确的答案。但是我们必须完全搜索每个子集，因为每个子集中的元素可能没有排序。
正确的解决方案涉及最大堆。我们从右下角的元素开始，将两个相邻的元素添加到堆中。每次我们从堆中提取最大元素并将新的相邻（左，上）元素添加到堆中。这样，我们实际上对矩阵进行排序以找到第 N 个元素。
于 2013-09-26T18:04:25.613 回答
1
将矩阵的每一行视为一个排序数组，并在每个数组上从右到左进行 m 路合并，直到找到第 N 个元素。时间复杂度为 O(N*logm)。
我不认为 vbmaster 提供的答案是正确的。您不能确保反对角水平始终大于其左上角水平。考虑以下示例：
1 2 3
3 4 5
7 8 9
使用 vbmaster 建议的顺序，它是：{9},{8,5},{7,4,3},{3,2},{1} 但是我们可以看到，第三组 {7,4 ,3} 有一个元素大于第二个集合（7>5），如果你用这个顺序找到第3个元素，你会得到5的答案；但正确答案是 7。
于 2015-01-03T21:36:10.353 回答