寻找从2-D数组排序第k最大元素 [英] Find kth largest element from a 2-d sorted array
问题描述
我有一个二维数组。行和列进行排序。如何找到从2-D数组中的第k最大元素？
I have a 2 dimensional array. The rows and columns are sorted. How to find the kth largest element from the 2-d array?
推荐答案
如果你有一个 N *ñ矩阵那么就有可能做到这一点在平均时间 O（N *的log（n）*的log（n））。
If you have an n * n matrix then it is possible to do this in average time O(n * log(n) * log(n)).
你要做的就是打破矩阵成一系列有序阵列，然后通过他们都做一个二进制搜索一次。例如假设 N = 4 并从索引（0,0）到（ 3,3）。我们可以把它分成了下去一列的上升斜线，然后右转完成行数组。这将使排序阵列我们以下设置：
What you do is break the matrix into a series of sorted arrays, then do a binary search through all of them at once. For instance suppose that n = 4 and is indexed from (0,0) to (3,3). We can break it into arrays that go down a column to the rising diagonal then turn right to finish the row. This would give us the following set of sorted arrays:
-
（0,0），（0,1），（0,2），（0,3），（1,3），（2,3），（3,3） -
（1,0），（1,1），（1,2），（2,2），（3,2） -
（2,0），（2,1），（3,1） -
（3,0）
(0,0), (0,1), (0,2), (0,3), (1,3), (2,3), (3,3)(1,0), (1,1), (1,2), (2,2), (3,2)(2,0), (2,1), (3,1)(3,0)
这为我们提供了 N 排序列出了矩阵。
This gives us n sorted lists out of the matrix.
因此，我们需要找出其中的 K '个元素是一组有序阵列。
So we need to figure out where the k'th element is in a set of sorted arrays.
我们将做到这一点与二进制搜索一下它的价值应该是。
We will do this with a binary search for what its value should be.
通过利用我们的时间最长的数组的中点，这将是（0,3）在这个例子中的元素开始。然后对于每个其它阵列找出多少大于，小于或等于该值。 （您可以用二进制搜索找到这一点。）这让我们找出其中的一侧划分 K '个元素是。如果我们只是选择了元素相匹配，我们找到了答案。否则，我们就可以扔掉每个阵列的平均半衰期（有时扔掉整个阵列）和重复。
Start by taking the midpoint of our longest array, which would be the element (0,3) in the example. Then for every other array figure out how many are bigger than, smaller than, or equal to this value. (You can find this by a binary search.) This let's us figure out which side of that divide the k'th element is on. If it matches the element we just chose, we have the answer. Otherwise we can throw away on average half of each array (sometimes throw away whole arrays) and repeat.
在平均 O（日志（N））的操作，每个成本 O（N日志（N））来执行，我们找到了答案，导致我估计上面。
After an average O(log(n)) operations, each of which costs O(n log(n)) to perform, we'll have the answer, leading to my estimate above.
这篇关于寻找从2-D数组排序第k最大元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
