在排序矩阵第K最小的元素 [英] Kth smallest element in sorted matrix

问题描述

这是一个面试问题。

的k ^日与排序的行和列的矩阵最小元素。
是不是很正确，在K ^日最小的元素是之一的[I，J] 等 I + J =氏/ code>？

Find the K^th smallest element in a matrix with sorted rows and columns.
Is it correct that the K^th smallest element is one of a[i, j] such as i + j = K ?

推荐答案

假。

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

Consider a simple matrix like this one:

1 3 5
2 4 6
7 8 9

9是最大的（第九最小）元素。但是，9是A [3,3]，以及3 + 3！= 9（不管索引约定，你使用，它不可能是真实的）。

9 is the largest (9th smallest) element. But 9 is at A[3, 3], and 3+3 != 9. (No matter what indexing convention you use, it cannot be true).

您可以通过逐步合并行，增加了一个堆有效地找到最小元素解决o这个问题（K log n）的时间。

You can solve this problem in O(k log n) time by merging the rows incrementally, augmented with a heap to efficiently find the minimum element.

基本上，你把第一列的元素放入堆，并跟踪他们来自该行。在每个步骤中，您从堆中的最小元素，并从它来自该行推的下一个元素（如果达到该行的末尾，那么你不推任何东西）。无论移除最小和添加新元素的成本为O（log n）的。在第j个步骤中，您删除Ĵ个最小的元素，所以在 K 步骤你的总成本完成对 0（K log n）的操作（其中n是行矩阵中的数字）。

Basically, you put the elements of the first column into a heap and track the row they came from. At each step, you remove the minimum element from the heap and push the next element from the row it came from (if you reach the end of the row, then you don't push anything). Both removing the minimum and adding a new element cost O(log n). At the jth step, you remove the jth smallest element, so after k steps you are done for a total cost of O(k log n) operations (where n is the number of rows in the matrix).

对于上面的矩阵，你最初用 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个迭代之后最小的元素。

For the matrix above, you initially start with 1,2,7 in the heap. You remove 1 and add 3 (since the first row is 1 3 5) to get 2,3,7. You remove 2 and add 4 to get 3,4,7. Remove 3 and add 5 to get 4,5,7. Remove 4 and add 6 to get 5,6,7. Note that we are removing the elements in the globally sorted order. You can see that continuing this process will yield the kth smallest element after k iterations.

（如果矩阵具有比列更多的行，然后在列进行操作，而不是以减小的运行时间。）

(If the matrix has more rows than columns, then operate on the columns instead to reduce the running time.)

这篇关于在排序矩阵第K最小的元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！