我有一个二维数组,行和列都已经排序。如何从这个二维数组中找到第k大的元素?
我有一个二维数组,行和列都已经排序。如何从这个二维数组中找到第k大的元素?
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))
,我们将得到答案,从而得出上述估计。log(n)
在里面。我们从sqrt(n)
个数组开始,但我怀疑大多数数组很快就会被排除掉。然而,第一次遍历的时间复杂度是O(sqrt(n) * log(n))
,所以我不会比这更好了。 - btilly在最小的维度上进行n路合并。当你取出第k个项目时,就完成了。
测试表明,此操作的运行时间为k lg d,其中d = min(rows, cols)。
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)
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)。rank(N,a) = k/2
和rank(N,b) = k/2 + n
。这显然可以在N上递归完成(相对于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矩阵)。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大的元素。
但我不确定这种方法的复杂度会是什么样子。
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))
假设一个有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个最大元素。
(1, 2), (1, 3), (1, 4), (2, 1), (2, 2), (3, 1), (4, 1)
。 - btilly