我有一个二维数组，行和列都已经排序。如何从这个二维数组中找到第k大的元素？
从二维排序数组中找到第k大的元素
15
- Paul Nibin
9
4如果这是一项作业练习，请标记为homework。 - Tomasz Nurkiewicz
6“行和列已排序”是什么意思？每行的开头是否在前一行的结尾之后，还是它们是独立排序的？ “行和列已排序”指的是每行和每列中的元素按升序或降序排列。每行的开头并不一定在前一行的结尾之后，每列也是如此。行和列可以独立排序。 - AShelly
这不是作业。是我朋友问我的问题。数组中的元素是独立排序的。如果你取数组中的任何一个元素，那么在它上面和左边的元素总是比它小。 - Paul Nibin
5有趣，我最近在一次面试中被问到了这个问题。 - MAK
2可能是搜索算法的重复问题。 - Aryabhatta
显示剩余4条评论
7个回答
5
如果您有一个
因此，我们需要确定一组已排序的数组中第
我们将使用二分查找来确定其值应该是多少。
首先，取我们最长数组的中点，这将是示例中的元素
经过平均
n * n 的矩阵，那么平均时间复杂度可以达到 O(n * log(n) * log(n))。具体操作是将矩阵分成一系列已排序的数组，然后同时在所有数组中进行二分查找。例如，假设 n = 4，从(0,0) 到 (3,3) 进行索引。我们可以将它分成沿着列向下到上升对角线然后向右转以完成行的数组。这将给我们以下一组已排序的数组：
(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个已排序的列表。因此，我们需要确定一组已排序的数组中第
k 个元素的位置。我们将使用二分查找来确定其值应该是多少。
首先，取我们最长数组的中点，这将是示例中的元素
(0,3)。然后，对于每个其他数组，找出有多少比它大、比它小或等于这个值的元素。（您可以通过二分查找来找到这个数量。）这让我们确定了第 k 个元素在哪一侧。如果它与我们刚选择的元素匹配，那么我们就得到了答案。否则，我们可以平均舍弃每个数组的一半（有时要舍弃整个数组）并重复此操作。经过平均
O(log(n)) 次操作，每次操作的成本为 O(n log(n))，我们将得到答案，从而得出上述估计。- btilly
8
1有趣！不过，运行时间很可能更难精确地获取，因为数组的大小不同且它们的输入不是独立的。我很好奇是否有一种中位数方案可以去除平均性。 - hugomg
@missingno：这就是为什么我说可能会有一个额外的因素
log(n)在里面。我们从sqrt(n)个数组开始，但我怀疑大多数数组很快就会被排除掉。然而，第一次遍历的时间复杂度是O(sqrt(n) * log(n))，所以我不会比这更好了。 - btilly@老程序员 最长剩余中位数是一个合理的选择。但是随机选择平均来说也可以很好地工作。 - btilly
由于给定的矩阵是一个二维排序矩阵，它的所有行（或列）已经排序，这些行（或列）只是你所说的“一组排序数组”，因此不需要按照描述中所述进行任何特殊的矩阵分解。 - nybon
@nybon 矩阵的分解并不是绝对必要的。但它确实方便地提供了一个非常好的起始分解点。 - btilly
显示剩余3条评论
3
在最小的维度上进行n路合并。当你取出第k个项目时，就完成了。
测试表明，此操作的运行时间为k lg d，其中d = min(rows, cols)。
- AShelly
5
抱歉，我不太明白您的意思。您所说的最小维度是什么意思？如果我没理解错的话，在归并排序中我们使用分治法。我们将一个数组分成两个部分，并对每个数组进行归并排序。归并排序再次将数组分成两个部分，并按排序顺序组合。我们需要递归地执行此操作，直到数组长度为1。对吗？ - Paul Nibin
抱歉，我的意思是只执行“合并”步骤。如果您的数组行数少于列数，请合并行。如果列数较少，请合并这些列。 - AShelly
谢谢您的回复。是的，我认为这会给我答案。归并排序的复杂度是(n log n)。有没有更低复杂度的方法？再次感谢。 - Paul Nibin
由于实际上您不必执行除法部分，并且在找到k个元素后可以停止，因此复杂度应该更像（k * c Lg c），其中c是列或行中较小的数字。请参见https://dev59.com/1W445IYBdhLWcg3wE2Je以获取n路合并算法。 - AShelly
参见 #https://dev59.com/mlbTa4cB1Zd3GeqP_o6x - AShelly
2
实际上，有一个时间复杂度为 O(n) 的分治算法可以解决已排序矩阵中的选择问题（即找到已排序矩阵中第 k 小的元素）。
Selection In X+Y and Matrices with Sorted Rows and Columns 的作者最初提出了这样一种算法，但它的工作原理并不那么直观。一个更简单的算法如下所示，可以在 Selection in a sorted matrix 中找到。
定义：假设有一个已排序的 n x m 矩阵 M，其中 n <= m 且没有重复项，我们可以定义一个子矩阵 N，使得 N 包含所有奇数列和 M 的最后一列。矩阵 M 中元素 e 的排名被定义为 rank(M,e) = |{M(i,j) | M(i,j) < e}|。
主要定理：该算法基于以下事实，即如果M是一个排序矩阵，则
证明：取
征服：换句话说，如果我们要在M中找到第k个排名的元素，我们只需要查看由元素a和b限定的M的子矩阵P，使得
“Divide”：唯一剩下的事情就是找到a和b，使得
“运行时间分析”：总的来说，我们有一个O(m)的征服算法。将
对于具有重复元素的矩阵的一般情况，可以使用行号和列号标记矩阵的元素。
定义：假设有一个已排序的 n x m 矩阵 M，其中 n <= m 且没有重复项，我们可以定义一个子矩阵 N，使得 N 包含所有奇数列和 M 的最后一列。矩阵 M 中元素 e 的排名被定义为 rank(M,e) = |{M(i,j) | M(i,j) < e}|。
主要定理：该算法基于以下事实，即如果M是一个排序矩阵，则
2*rank(N,e) - 2n <= rank(M,e) <= 2*rank(N,e)。证明：取
f(i) = min j s.t. M(i,j) >= e，我们可以得出结论。rank(M,e) = sum i=1 to n of f(i)
rank(N,e) = sum i=1 to n of ceil(f(i)/2) <= rank(M,e)/2 + n
=> 2*rank(N,e) - 2n <= rank(M,e)
rank(N,e) > sum i=1 to n of f(i)/2
=> rank(M,e) <= 2*rank(N,e)
征服：换句话说，如果我们要在M中找到第k个排名的元素，我们只需要查看由元素a和b限定的M的子矩阵P，使得
rank（N，a）= floor（k/2）和rank（N，b）= ceil（k/2）+ n 。这个子矩阵有多少个元素？根据前面的不等式和没有重复项的假设，至多为O（n）。因此，我们只需在P中选择第k-rank（N，a）个元素，这可以通过将P重新排列成排序数组来完成，时间复杂度为O（m），然后运行像快速选择这样的线性时间算法来找到实际元素。rank（M，a）可以在O（m）内计算，从矩阵中最小的元素开始，并迭代列，直到找到大于a的元素，然后进入下一行并向前一列移动，直到找到第一个大于a的元素等等。因此，征服部分的时间复杂度为O（m）。“Divide”：唯一剩下的事情就是找到a和b，使得
rank(N,a) = k/2和rank(N,b) = k/2 + n。这显然可以在N上递归完成（相对于M，其大小减半）。“运行时间分析”：总的来说，我们有一个O(m)的征服算法。将
f(n,m)作为n x m矩阵的算法复杂度，其中n <= m（如果不是，矩阵可以概念上旋转），我们可以建立递归关系f(m) = c*m + f(m/2)。根据主定理，由于f(1) = 1，我们发现f(n,m) = O(m)。因此，整个算法的运行时间为O(m)，在方阵的情况下为O(n)（这也是O(k)，因为我们可以限制搜索范围为包含前k列和行的k x k矩阵）。对于具有重复元素的矩阵的一般情况，可以使用行号和列号标记矩阵的元素。
- Jean Gauthier
2
假设我有如下矩阵：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
当我在思考这个问题的解决方案时，我发现第一个最大的元素总是在(4,4)。第二个最大的元素将在(3,4)或(4,3)，并且不能在(4,4)。因此，我在思考是否可以根据矩阵大小和k找到可能的第k大元素的位置。
假设可能的第k大元素的位置集合为f(size(matrix), k)。
但在下面发布的答案中，我找不到一个简单的函数f()，它可以生成可能的位置。
而且，我只能检查可能位置的元素，而不是检查所有位置的元素。
要找到大于一个元素的数字，我们可以使用以下方法。
如果我想找到有多少个元素大于14。无论如何，在14的右侧(15)和14的下方(19,24)以及它们之间的所有元素(20,25)都大于14，因为行和列已经排序。然后，在14的上方有2个子矩阵(包括5和10)，在14的下方有一个子矩阵(包括16、17、18、21、22、23)，它们可能包含大于14的元素，也可能不包含。因此，如果我们从这3个矩阵中找到并添加大于14的元素的数量，就可以得到大于14的元素数量。
对于每个可能的位置，我们都可以在矩阵中找到比它大的元素数量。如果有k-1个更大的元素，则当前位置的元素是第k大的元素。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
当我在思考这个问题的解决方案时，我发现第一个最大的元素总是在(4,4)。第二个最大的元素将在(3,4)或(4,3)，并且不能在(4,4)。因此，我在思考是否可以根据矩阵大小和k找到可能的第k大元素的位置。
假设可能的第k大元素的位置集合为f(size(matrix), k)。
但在下面发布的答案中，我找不到一个简单的函数f()，它可以生成可能的位置。
而且，我只能检查可能位置的元素，而不是检查所有位置的元素。
要找到大于一个元素的数字，我们可以使用以下方法。
如果我想找到有多少个元素大于14。无论如何，在14的右侧(15)和14的下方(19,24)以及它们之间的所有元素(20,25)都大于14，因为行和列已经排序。然后，在14的上方有2个子矩阵(包括5和10)，在14的下方有一个子矩阵(包括16、17、18、21、22、23)，它们可能包含大于14的元素，也可能不包含。因此，如果我们从这3个矩阵中找到并添加大于14的元素的数量，就可以得到大于14的元素数量。
对于每个可能的位置，我们都可以在矩阵中找到比它大的元素数量。如果有k-1个更大的元素，则当前位置的元素是第k大的元素。
package test;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class NewTest
{
private static int matrixSize = 25;
private static Map < Integer, List < Point > > largestEltVsPossiblePositions = new HashMap < Integer, List < Point >>();
static
{
// In the initialize method, I am populating the map
// "largestEltVsPossiblePositions" with kth largest element and its
// possible positions. That is 1st largest element will always be in
// (24,24) and 2nd largest element will be (23,24) and (24,23). Like
// that I am populating the possible locations for all the nth largest
// elements. This map we need to initialize only once.
initialize();
}
private static void initialize()
{
for ( int i = 1; i <= matrixSize * matrixSize; i++ )
{
//Getting the possible locations for each number and putting in the map.
List < Point > possiblePositions = getPossiblePositions( matrixSize, i );
largestEltVsPossiblePositions.put( i, possiblePositions );
}
}
/**
* @param args
*/
public static void main( String [] args )
{
// int matrixSize = 5;
// for ( int i = 1; i <= matrixSize * matrixSize; i++ )
// {
// List < Point > possiblePositions = getPossiblePositions( matrixSize, i );
// System.out.println( i + " --- " + possiblePositions.size() + " - " + possiblePositions );
// }
//creating a test array.
int [][] matrix = createTestArray();
long currentTimeMillis = System.currentTimeMillis();
findKthLargestElement( matrix, 7 );
System.out.println( "Total time : " + ( System.currentTimeMillis() -
currentTimeMillis ) );
currentTimeMillis = System.currentTimeMillis();
findKthLargestElement( matrix, 27 );
System.out.println( "Total time : " + ( System.currentTimeMillis() -
currentTimeMillis ) );
currentTimeMillis = System.currentTimeMillis();
findKthLargestElement( matrix, 34 );
System.out.println( "Total time : " + ( System.currentTimeMillis() -
currentTimeMillis ) );
currentTimeMillis = System.currentTimeMillis();
findKthLargestElement( matrix, 624 );
System.out.println( "Total time : " + ( System.currentTimeMillis() -
currentTimeMillis ) );
currentTimeMillis = System.currentTimeMillis();
findKthLargestElement( matrix, 2 );
System.out.println( "Total time : " + ( System.currentTimeMillis() -
currentTimeMillis ) );
currentTimeMillis = System.currentTimeMillis();
findKthLargestElement( matrix, 4 );
System.out.println( "Total time : " + ( System.currentTimeMillis() -
currentTimeMillis ) );
currentTimeMillis = System.currentTimeMillis();
findKthLargestElement( matrix, 310 );
System.out.println( "Total time : " + ( System.currentTimeMillis() -
currentTimeMillis ) );
}
private static int [][] createTestArray()
{
int [][] matrix = new int [matrixSize] [matrixSize];
int count = 1;
for ( int i = 0; i < matrixSize; i++ )
{
for ( int j = 0; j < matrixSize; j++ )
{
matrix[j][i] = count;
count++ ;
}
}
return matrix;
}
private static void findKthLargestElement( int [][] matrix, int k )
{
//Get all the possible positions of this kth largest element.
List < Point > possiblePoints = largestEltVsPossiblePositions.get( k );
//I am sorting the points in descending order of the values in them.
Collections.sort( possiblePoints, new PointComparator( matrix ) );
for ( Point point : possiblePoints )
{
//For a point, If there are exactly k-1, larger elements in the matrix, then it is the kth largest element.
if ( ( k - 1 ) == getNoofLargerElementsThanKFromMatrix( matrix, point ) )
{
System.out.println( "Largest " + k + "th element in the matrix is : " + matrix[point.x][point.y]
+ " in the co-ordinates : " + point );
break;
}
}
}
/*
* This method will find the elements larger than the element at the specified point from the matrix.
*/
private static int getNoofLargerElementsThanKFromMatrix( int [][] matrix, Point point )
{
int sum = 0;
// Suppose the point is (x,y). Then all the elements (x+1,y),
// (x+2,y).... (maxRows,y), (x,y+1), (x,y+2), ... (x,maxCols) and all
// the numbers between them(x+1,y+1), (x+2,y+1)... (maxRows,maxCols)
// will be surely greater than the element at the point (x,y.). We are counting those element.
sum = ( matrixSize - point.x ) * ( matrixSize - point.y ) - 1;
if ( point.x > 0 )
{
// In the above case, we were sure that all the elements in that range are greater than element at the point.
// There is a region in the matrix where there might be elements larger than the element at the point.
// If the point is (x,y), then the elements from (0,y+1) to
// (x-1,maxCols), In this region there might be some elements which
// are larger than the element we need to count those.
sum = sum + getNumbersGreaterThanKFromUpperMatrix( matrix, point );
}
if ( point.x < matrix.length - 1 )
{
// It is same as the above case, There is another region in the
// matrix where there might be elements larger than the element at the point.
// If the point is (x,y), then the elements from (x+1,0) to
// (maxRows,y-1), In this region there might be some elements which
// are larger than the element we need to count those.
sum = sum + getNumbersGreaterThanKFromLowerMatrix( matrix, point );
}
//Once we get all the elements larger than k, we can return it.
return sum;
}
private static int getNumbersGreaterThanKFromUpperMatrix( int [][] matrix, Point point )
{
int startY = point.y;
if ( point.y + 1 != matrix[0].length )
{
startY = point.y + 1;
}
Point matrixStart = new Point( 0, startY );
int startX = point.x;
if ( point.x != 0 )
{
startX = point.x - 1;
}
Point matrixEnd = new Point( startX, matrix[0].length - 1 );
return getLargerElementsFromTheMatrix( matrix, matrixStart, matrixEnd, matrix[point.x][point.y] );
}
private static int getNumbersGreaterThanKFromLowerMatrix( int [][] matrix, Point point )
{
int startX = point.x;
if ( point.x + 1 != matrix.length )
{
startX = point.x + 1;
}
Point matrixStart = new Point( startX, 0 );
int startY = point.y;
if ( point.y != 0 )
{
startY = point.y - 1;
}
Point matrixEnd = new Point( matrix.length - 1, startY );
return getLargerElementsFromTheMatrix( matrix, matrixStart, matrixEnd, matrix[point.x][point.y] );
}
private static int getLargerElementsFromTheMatrix( int [][] matrix, Point matrixStart, Point matrixEnd, int elt )
{
//If it is a single cell matrix, just check that element in the matrix is larger than the kth element we are checking.
if ( matrixStart.equals( matrixEnd ) )
{
if ( elt <= matrix[matrixStart.x][matrixStart.y] )
{
return 1;
}
else
{
return 0;
}
}
if ( elt <= matrix[matrixStart.x][matrixStart.y] )
{
return ( matrixEnd.x - matrixStart.x + 1 ) * ( matrixEnd.y - matrixStart.y + 1 );
}
else
{
//Do it recursively to get all the elements larger than elt from the matrix from the startPoint to endPoint.
int matrixStartX = matrixStart.x;
if ( matrixStart.x + 1 <= matrixEnd.x )
{
matrixStartX = matrixStart.x + 1;
}
int matrixStartY = matrixStart.y;
if ( matrixStart.y + 1 <= matrixEnd.y )
{
matrixStartY = matrixStart.y + 1;
}
Point newMatrixStart = new Point( matrixStartX, matrixStartY );
int s1 = getLargerElementsFromTheMatrix( matrix, newMatrixStart, matrixEnd, elt );
int s2 = getLargerElementsFromTheMatrix( matrix, new Point( matrixStartX, matrixStart.y ), new Point(
matrixEnd.x, matrixStart.y ), elt );
int s3 = getLargerElementsFromTheMatrix( matrix, new Point( matrixStart.x, matrixStartY ), new Point(
matrixStart.x, matrixEnd.y ), elt );
return s1 + s2 + s3;
}
}
//For getting the possible positions of kth largest element.
private static List < Point > getPossiblePositions( int matrixSize, int k )
{
List < Point > points = new ArrayList < Point >();
k-- ;
for ( int i = 0; i < matrixSize; i++ )
{
for ( int j = 0; j < matrixSize; j++ )
{
int minNoGreaterThanIJ = ( matrixSize - i ) * ( matrixSize - j ) - 1;
int maxNoGreaterThanIJ = matrixSize * matrixSize - ( ( i + 1 ) * ( j + 1 ) );
if ( minNoGreaterThanIJ <= k && maxNoGreaterThanIJ >= k )
points.add( new Point( i, j ) );
}
}
return points;
}
}
class Point
{
final int x;
final int y;
Point( int x, int y )
{
this.x = x;
this.y = y;
}
@Override
public String toString()
{
return "(" + x + "," + y + ")";
}
@Override
public int hashCode()
{
final int prime = 31;
int result = 1;
result = prime * result + x;
result = prime * result + y;
return result;
}
@Override
public boolean equals( Object obj )
{
if ( this == obj )
return true;
if ( obj == null )
return false;
if ( getClass() != obj.getClass() )
return false;
Point other = ( Point ) obj;
if ( x != other.x )
return false;
if ( y != other.y )
return false;
return true;
}
}
class PointComparator implements Comparator < Point >
{
private final int [][] matrix;
public PointComparator( int [][] matrix )
{
this.matrix = matrix;
}
@Override
public int compare( Point o1, Point o2 )
{
if ( matrix[o1.x][o1.y] == matrix[o2.x][o2.y] )
{
return -1;
}
else if ( matrix[o1.x][o1.y] < matrix[o2.x][o2.y] )
{
return 1;
}
else
{
return 1;
}
}
}
初始化只在开始时进行一次。完成初始化后，可能的位置将被计算并缓存。这些信息可以用于查找第K大的元素。
但我不确定这种方法的复杂度会是什么样子。
- Paul Nibin
1
这个怎么样？
假设：
1. 行和列按升序排列。 2. 我们需要在m*n个数字中找到第k小的数字（这是问题陈述）。 3. 如果m*n < k，则返回null/引发异常。
维护一个大小为k的最大堆。
假设：
1. 行和列按升序排列。 2. 我们需要在m*n个数字中找到第k小的数字（这是问题陈述）。 3. 如果m*n < k，则返回null/引发异常。
维护一个大小为k的最大堆。
Push A[0][0] in the heap.
for i = 1 to k
curr_element = pop max element from heap
Push the right and bottom neighbor of the popped element from the matrix
(if they exist and have not been pushed earlier)
return curr_element
时间复杂度 = 循环运行 k 次 (O(k)) * 1 次迭代运行 O(3*log(k)) 次 = O(k*log(k))
- Him
-1
假设一个有r行和c列的数组。索引从1开始。
更新：抱歉，我忘记提到首先您必须将k转换为以下公式才能起作用：
k = n - (k-1)。其中n是元素的总数，即r*c。
您可以获得第k个最大元素的行索引：ceil(k/r)
您可以获得第k个最大元素的列索引：k%c（%是Mod运算符）
更新：如果k%c = 0，则将结果设置为c。
运行时间为O(1)。
如果您有一个k=14的r=4和c=4的数组
k = 16 - (14 - 1)
k= 3
ARR[ceil(3/4),3%c]将返回第k个最大元素。
- Enrique
11
如果允许在数组中有重复项，那么这种方法将无法工作，而我认为这正是这里的情况... - gusbro
我有一个3x3的数组。{{1,2,3},{4,5,6},{7,8,9}}。我想找到第二大的元素。在这种情况下，第二大的元素是8，位置是a(3,2)，如果索引从(1,1)开始，或者是a(2,1)，如果索引从(0,0)开始。通过解决方案，第二大的元素应该是a(2/3,2%3)，那么应该是a(0,2)吗？这似乎不正确。而且我认为，应该处理重复值。我的朋友没有提到任何关于重复值的事情。 - Paul Nibin
@Paul Nibin 是的，那样做不行，因为10不在正确的位置。你说：如果你取数组中的任何一个元素，它上面和左边的元素总是比该元素小。所以这个数组与你之前的评论相矛盾。例如，如果你取8，10和9在上面，但它们并不比8小。 - Enrique
这根本行不通。假设在一个10 x 10的矩阵中，k = 4。那么第k大的元素可能在以下任意7个单元格中：
(1, 2), (1, 3), (1, 4), (2, 1), (2, 2), (3, 1), (4, 1)。 - btilly我觉得我的问题表述不够清晰。当我说“上面的元素”时，我指的是该元素所在列上方的元素。如果你取数字8，那么8上面的元素就是5和2。我的意思是，无论你取哪一行或哪一列，它们都是按照顺序排列的。 - Paul Nibin
显示剩余6条评论
-1
方法：
1. 复制每个节点并将其插入到原始节点的右侧。
2. 复制随机指针。
3. 复制左指针。
4. 分离两棵树。
有关图形说明，请参阅http://mytechspaze.com/index.php/2016/09/15/clone-binary-tree/。
有关图形说明，请参阅http://mytechspaze.com/index.php/2016/09/15/clone-binary-tree/。
- vikas_boundless
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接