java - 具有排序的行和列的矩阵中第K个最小的元素

Question

This question already has answers here:

Selection algorithms on sorted matrix
                                
                                    （8个答案）
                                
                        
                        
                             Kth smallest element in sorted matrix
                                
                                    （7个答案）
                                
                        
                                6年前关闭。
            
                    
按行和列排序的矩阵。我们需要从给定的矩阵中找到 Kth最小元素。

有时间复杂度 O(KlogM)的解决方案，但需要线性时间算法来解决该问题。

矩阵示例：

1   3    5
2   4    6
7   8    9

假设M =行数，N =列数和 M<N。

我的解决方案：


  
  通过获取所有 matrix[i][0]元素来创建大小为M的堆。
  找到最小的元素，然后从相应的行中推送下一个元素。
  重复第二步，直到找到 Kth最小。

最佳答案

Frederickson和Johnson算法的工作原理大致如下。 （它总是使我想起Quickselect。）这是来自使用不同实现作为模板的实现，因此细节可能与他们的论文有些不同，但是时间复杂度和想法相同。我假设k的合法值是从0到M * N - 1。

我们将以i（从0开始）访问第j行和第A[i, j]列中的元素。另外，我们将假装可以访问负无穷大的A[i, -1]和正无穷大的A[i, N]。我们维护两个由索引left[0 .. M)和right[0..M)组成的数组，以及两个变量lessthanleft和greaterthanright，它们具有以下属性：


存在一个矩阵元素A[i0, j0]，因此对于所有i行，我们都有A[i, left[i] - 1] < A[i0, j0] <= A[i, left[i]]。也就是说，left[i]大致是A[i0, j0]在行i中的位置。
对于从left[i]到i的0，值M - 1的总和为lessthanleft。请注意，lessthanleft是在left所指示位置左侧的位置中的矩阵元素的数量，即，严格小于A[i0, j0]的矩阵元素。
lessthanleft <= k。因此，这表示我们正在寻找的元素位于i右侧的left[i]行中。
存在一个矩阵元素A[i1, j1]，因此对于所有i行，我们都有A[i, right[i] - 1] < A[i1, j1] <= A[i, right[i]]。也就是说，right[i]大致是A[i1, j1]在行i中的位置。
对于从N - right[i]到i的0，值M - 1的总和为greaterthanright。请注意，greaterthanright是在right所指示位置右边的位置中的矩阵元素的数量，即，严格大于A[i1, j1]的矩阵元素。
greaterthanright <= M * N - k。因此，这表示我们正在寻找的元素位于i左侧的right[i]行中。


可以通过将left的每个元素设置为0，将right的每个元素设置为N并将lessthanleft和greaterthanright都设置为0来初始化这些属性-除非k = 0（在哪种情况下我们返回A[0, 0]）或k = M*N - 1（这种情况下我们返回A[M-1, N-1]）。顺便说一下，这对应于i0=0，j0=0，i1=M-1，j1=N-1。

现在，在每个迭代中，我们用A[i2, j2]选择一个枢轴矩阵元素left[i2] <= j2 < right[i2]。 （有几种策略；我将在下面讨论。）我们使用数组less[0..M)和lessequal[0..M)填充下面的内部循环，并将变量nless和nequal和ngreater设置为0。在内部循环中，我们遍历所有行i，并将less[i]和lessequal[i]设置为A[i, less[i] - 1] < A[i2, j2] <= A[i, less[i]]和A[i, lessequal[i] - 1] <= A[i2, j2] < A[i, lessequal[i]]。 （由于less[i-1] >= less[i]，您可以使用less[i-1]和lessequal[i-1]的值，并从那里开始向左线性搜索，以使整个过程花费O(N)的时间。）在每个这样的步骤之后，我们将less[i] - left[i]添加到< cc>，将nless添加到lessequal[i] - less[i]，然后将nequal添加到right[i] - lessequal[i]。

在此内循环之后，我们检查是否为ngreater。在这种情况下，我们通过将lessthanleft + nless >= k设置为A[i2, j2]继续处理小于right的条目（如果希望防止在循环中为数组分配指针，请进行指针翻转，或者从 到 less），将 less设为 right，并继续进行下一个迭代。如果为 greaterthanright，则通过将 greaterthanright + ngreater + nequal设置为 lessthanleft + nless + nequal < k，将 A[i2, j2]设置为 left，并继续进行下一次迭代，从而继续输入大于 lessequal的条目。否则，我们要查找的条目在等于 lessthanleft的条目中，因此我们返回 lessthanleft + nless + nequal。

现在开始选择枢轴。一种方法是在间隔 A[i2, j2]中选择一个随机数 A[i2, j2]；然后，通过从 c开始的每个 [0 .. N * M - lessthanleft - greaterthanright)从 c减去 left直到它变为负数，我们找到包含 right和 left[i] - right[i]之间的第 c个矩阵元素的行。现在，选择 i变为负数，然后让 0。或者，您可以对每行中其余条目的中位数进行中位数中位数样式计算。

因此，通常，每行 i和 j = round((left[i] + right[i])/2)之间的矩阵元素集会被拆分，希望每次迭代时将其分解成大约一半。复杂度分析与 Quickselect相似，其中预期的迭代次数“几乎可以肯定”（从数学意义上来说）是初始池中值数目的对数。通过使用中位数样式风格的枢轴选择，我相信您可以在实际运行时为它付出代价的同时确定地实现这一目标，但是现在我假设“几乎可以肯定”已经足够了。 （在相同的条件下，Quicksort为O（N lg（N））。）任何单个迭代都需要 left[i]时间来选择一个轴，然后在内部循环中花费 right[i]时间。候选者的初始池具有 O(M)个成员，因此，迭代次数几乎可以肯定是 O(N)，而总复杂度为 M*N。对每行使用一个带有条目的堆的算法使用 O(lg(M * N)) = O(lg(M) + lg(M))，这要糟糕得多，因为 O(N * (lg(M) + lg(N)))仅受 O(k * lg(M))限制。



这是一个简单的示例：考虑 k， N*M，我们需要从矩阵 M=4中选择第 N=5个元素，如下所示：

 6 12 17 17 25
 9 15 17 19 30
16 17 23 29 32
23 29 35 35 39

我们将 k=11初始化为 A，将 left初始化为 [0,0,0,0]， right和 [5,5,5,5]都为 lessthanleft。

假设对于第一次迭代，我们选择 greaterthanright作为枢轴。在内部循环期间，我们开始检查条目 0左侧的第一行，找到第一个出现的最大为 A[1, 2]=17的数字。这在 right[0]-1=4列中，因此我们设置 17。现在，我们继续搜索严格小于 3的数字的首次出现；这发生在列 lessequal[0]=3+1=4中，因此我们设置 17。对于下一行，我们可以在列 1处开始寻找一个最大为 less[0]=1+1=2的值，然后在列 17中找到它，因此设置 lessequal[0]。从 2开始寻找一个严格小于 lessequal[1]=2+1=3的值，我们设置 17。继续我们得到 less[0]和 less[1] = 2。因此， less = [2,2,1,0]， lessequal = [4,3,2,0]和 nless = 5。我们有 nequal = 4，因此我们继续输入大于 ngreater = 11的条目，并设置 lessthanleft + nless + nequal = 9 < 11和 17。

对于下一次迭代，我们需要在 left = lessequal = [4,3,2,0]和 lessthanleft = 9之间的中心的某行 i上选择一个枢轴。也许我们选择 left[i]行，这意味着我们有 right[i]。在内部循环中，我们现在通过 2和 A[2,3] = 29和 less = [5,4,3,1]获得 lessequal = [5,4,4,2]和 nless = 4。现在为 nequal = 2，因此我们继续输入少于 ngreater = 5的条目，并设置 lessthanleft + nless = 13 > 11和 29。

对于第三次迭代，现在每行仅剩一个条目。我们随机选择一行-也许是 right = less = [5,4,3,1]行。枢轴是 greaterthanright = 7。在内部循环中，我们得到 3和 A[3,0] = 23。因此， less = [4,4,2,0]， lessequal = [4,4,3,1]和 nless = 1。现在，我们有了 nequal = 2，因此我们返回 ngreater = 1。实际上，有10个矩阵条目严格小于 lessthanleft + nless = 10 < k = 11 <= lessthanleft + nless + nequal = 12（在最后一次迭代中位于 23左侧的那些）和12个矩阵条目至多是 23（在最后一次迭代中位于 A[i, less[i]]左侧的那些）迭代）。

关于java - 具有排序的行和列的矩阵中第K个最小的元素，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19028613/

上一篇：java - 如何设置 ANDROID_HOME 环境变量？

下一篇：java - 创建了 Spring 单例类实例？

Answer 1

Frederickson和Johnson算法的工作原理大致如下。 （它总是使我想起Quickselect。）这是来自使用不同实现作为模板的实现，因此细节可能与他们的论文有些不同，但是时间复杂度和想法相同。我假设k的合法值是从0到M * N - 1。

我们将以i（从0开始）访问第j行和第A[i, j]列中的元素。另外，我们将假装可以访问负无穷大的A[i, -1]和正无穷大的A[i, N]。我们维护两个由索引left[0 .. M)和right[0..M)组成的数组，以及两个变量lessthanleft和greaterthanright，它们具有以下属性：


存在一个矩阵元素A[i0, j0]，因此对于所有i行，我们都有A[i, left[i] - 1] < A[i0, j0] <= A[i, left[i]]。也就是说，left[i]大致是A[i0, j0]在行i中的位置。
对于从left[i]到i的0，值M - 1的总和为lessthanleft。请注意，lessthanleft是在left所指示位置左侧的位置中的矩阵元素的数量，即，严格小于A[i0, j0]的矩阵元素。
lessthanleft <= k。因此，这表示我们正在寻找的元素位于i右侧的left[i]行中。
存在一个矩阵元素A[i1, j1]，因此对于所有i行，我们都有A[i, right[i] - 1] < A[i1, j1] <= A[i, right[i]]。也就是说，right[i]大致是A[i1, j1]在行i中的位置。
对于从N - right[i]到i的0，值M - 1的总和为greaterthanright。请注意，greaterthanright是在right所指示位置右边的位置中的矩阵元素的数量，即，严格大于A[i1, j1]的矩阵元素。
greaterthanright <= M * N - k。因此，这表示我们正在寻找的元素位于i左侧的right[i]行中。


可以通过将left的每个元素设置为0，将right的每个元素设置为N并将lessthanleft和greaterthanright都设置为0来初始化这些属性-除非k = 0（在哪种情况下我们返回A[0, 0]）或k = M*N - 1（这种情况下我们返回A[M-1, N-1]）。顺便说一下，这对应于i0=0，j0=0，i1=M-1，j1=N-1。

现在，在每个迭代中，我们用A[i2, j2]选择一个枢轴矩阵元素left[i2] <= j2 < right[i2]。 （有几种策略；我将在下面讨论。）我们使用数组less[0..M)和lessequal[0..M)填充下面的内部循环，并将变量nless和nequal和ngreater设置为0。在内部循环中，我们遍历所有行i，并将less[i]和lessequal[i]设置为A[i, less[i] - 1] < A[i2, j2] <= A[i, less[i]]和A[i, lessequal[i] - 1] <= A[i2, j2] < A[i, lessequal[i]]。 （由于less[i-1] >= less[i]，您可以使用less[i-1]和lessequal[i-1]的值，并从那里开始向左线性搜索，以使整个过程花费O(N)的时间。）在每个这样的步骤之后，我们将less[i] - left[i]添加到< cc>，将nless添加到lessequal[i] - less[i]，然后将nequal添加到right[i] - lessequal[i]。

在此内循环之后，我们检查是否为ngreater。在这种情况下，我们通过将lessthanleft + nless >= k设置为A[i2, j2]继续处理小于right的条目（如果希望防止在循环中为数组分配指针，请进行指针翻转，或者从 到 less），将 less设为 right，并继续进行下一个迭代。如果为 greaterthanright，则通过将 greaterthanright + ngreater + nequal设置为 lessthanleft + nless + nequal < k，将 A[i2, j2]设置为 left，并继续进行下一次迭代，从而继续输入大于 lessequal的条目。否则，我们要查找的条目在等于 lessthanleft的条目中，因此我们返回 lessthanleft + nless + nequal。

现在开始选择枢轴。一种方法是在间隔 A[i2, j2]中选择一个随机数 A[i2, j2]；然后，通过从 c开始的每个 [0 .. N * M - lessthanleft - greaterthanright)从 c减去 left直到它变为负数，我们找到包含 right和 left[i] - right[i]之间的第 c个矩阵元素的行。现在，选择 i变为负数，然后让 0。或者，您可以对每行中其余条目的中位数进行中位数中位数样式计算。

因此，通常，每行 i和 j = round((left[i] + right[i])/2)之间的矩阵元素集会被拆分，希望每次迭代时将其分解成大约一半。复杂度分析与 Quickselect相似，其中预期的迭代次数“几乎可以肯定”（从数学意义上来说）是初始池中值数目的对数。通过使用中位数样式风格的枢轴选择，我相信您可以在实际运行时为它付出代价的同时确定地实现这一目标，但是现在我假设“几乎可以肯定”已经足够了。 （在相同的条件下，Quicksort为O（N lg（N））。）任何单个迭代都需要 left[i]时间来选择一个轴，然后在内部循环中花费 right[i]时间。候选者的初始池具有 O(M)个成员，因此，迭代次数几乎可以肯定是 O(N)，而总复杂度为 M*N。对每行使用一个带有条目的堆的算法使用 O(lg(M * N)) = O(lg(M) + lg(M))，这要糟糕得多，因为 O(N * (lg(M) + lg(N)))仅受 O(k * lg(M))限制。



这是一个简单的示例：考虑 k， N*M，我们需要从矩阵 M=4中选择第 N=5个元素，如下所示：

 6 12 17 17 25
 9 15 17 19 30
16 17 23 29 32
23 29 35 35 39

我们将 k=11初始化为 A，将 left初始化为 [0,0,0,0]， right和 [5,5,5,5]都为 lessthanleft。

假设对于第一次迭代，我们选择 greaterthanright作为枢轴。在内部循环期间，我们开始检查条目 0左侧的第一行，找到第一个出现的最大为 A[1, 2]=17的数字。这在 right[0]-1=4列中，因此我们设置 17。现在，我们继续搜索严格小于 3的数字的首次出现；这发生在列 lessequal[0]=3+1=4中，因此我们设置 17。对于下一行，我们可以在列 1处开始寻找一个最大为 less[0]=1+1=2的值，然后在列 17中找到它，因此设置 lessequal[0]。从 2开始寻找一个严格小于 lessequal[1]=2+1=3的值，我们设置 17。继续我们得到 less[0]和 less[1] = 2。因此， less = [2,2,1,0]， lessequal = [4,3,2,0]和 nless = 5。我们有 nequal = 4，因此我们继续输入大于 ngreater = 11的条目，并设置 lessthanleft + nless + nequal = 9 < 11和 17。

对于下一次迭代，我们需要在 left = lessequal = [4,3,2,0]和 lessthanleft = 9之间的中心的某行 i上选择一个枢轴。也许我们选择 left[i]行，这意味着我们有 right[i]。在内部循环中，我们现在通过 2和 A[2,3] = 29和 less = [5,4,3,1]获得 lessequal = [5,4,4,2]和 nless = 4。现在为 nequal = 2，因此我们继续输入少于 ngreater = 5的条目，并设置 lessthanleft + nless = 13 > 11和 29。

对于第三次迭代，现在每行仅剩一个条目。我们随机选择一行-也许是 right = less = [5,4,3,1]行。枢轴是 greaterthanright = 7。在内部循环中，我们得到 3和 A[3,0] = 23。因此， less = [4,4,2,0]， lessequal = [4,4,3,1]和 nless = 1。现在，我们有了 nequal = 2，因此我们返回 ngreater = 1。实际上，有10个矩阵条目严格小于 lessthanleft + nless = 10 < k = 11 <= lessthanleft + nless + nequal = 12（在最后一次迭代中位于 23左侧的那些）和12个矩阵条目至多是 23（在最后一次迭代中位于 A[i, less[i]]左侧的那些）迭代）。