arrays - 已排序矩阵中的第 K 个最小元素

Question

这是一道面试题。

在已排序的行和列的矩阵中找到第 K 个最小元素。
第 K^th 最小元素是 a[i, j] 之一，例如 i + j = K 是否正确？

Answer 1

错误。

考虑一个像这样的简单矩阵:

1 3 5
2 4 6
7 8 9

9 是最大的(第 9 小的)元素。但是 9 位于 A[3, 3]，并且 3+3 != 9。(无论您使用什么索引约定，它都不可能是真的)。​​

---

您可以在 O(k log n) 时间内解决此问题，方法是逐步合并行，并增加堆以有效地找到最小元素。

基本上，您将第一列的元素放入堆中并跟踪它们来自的行。在每一步中，您从堆中移除最小元素并从它来自的行中推送下一个元素(如果您到达该行的末尾，那么您不会推送任何内容)。删除最小值和添加新元素的成本均为 O(log n)。在第 j 步，您删除了第 j 个最小元素，因此在 k 步之后，您的总成本为 O(k log n) 操作(其中 n 是矩阵中的行数)。

对于上面的矩阵，您最初从堆中的 1,2,7 开始。您删除 1 并添加 3(因为第一行是 1 3 5)以获得 2,3,7。您删除 2 并添加 4 以获得 3,4,7。删除 3 并添加 5 以获得 4,5,7。删除 4 并添加 6 以获得 5,6,7。请注意，我们正在删除全局排序顺序中的元素。您可以看到，继续此过程将在 k 次迭代后产生第 k 个最小元素。

(如果矩阵的行数多于列数，则改为对列进行操作以减少运行时间。)