У меня есть 2-мерный массив. Строки и столбцы сортируются. Как найти k-й наибольший элемент из 2-мерного массива?
Найти k-й наибольший элемент из 2-го сортированного массива
Ответ 1
Если у вас есть матрица 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)) для выполнения, у нас будет ответ, который приведет к моей оценке выше.
Ответ 2
Сделайте n-образное слияние по наименьшему размеру. Когда вы снимаете k-й элемент, вы закончили.
Тестирование показывает, что это работает в k lg d, где d = min (rows, cols).
Ответ 3
Предположим, что у меня есть матрица, как показано ниже
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 (размер (матрица), k).
Но в ответе, опубликованном ниже, я не мог найти простую функцию f(), которая может дать генерировать возможные местоположения.
И вместо проверки элементов во всех местах я могу проверять только элементы из возможных мест.
Для нахождения чисел, больших, чем элемент, мы можем использовать следующий способ.
Если я хочу найти, сколько элементов больше 14. Во всяком случае, элементы в правой части 14 (15) и под 14 (19,24) и все элементы между ними (20,25) являются больше 14. Когда строки и столбцы сортируются. Тогда есть 2 подматрицы над 14 (которая включает 5 и 10) и одну ниже 14 (которая включает 16, 17, 18, 21, 22, 23), которая может содержать или не содержать элементы, большие 14. Так что если мы найдем и добавьте количество элементов, большее 14 из этих 3-х матриц, у нас будет no элементов больше 14.
Для каждого возможного положения мы могли бы найти no из более крупных элементов в матрице. Если есть 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-го наибольшего элемента.
Но я не уверен, какая будет сложность этого метода.
Ответ 4
Как насчет этого?
Полагая
- Строки и столбцы находятся в порядке возрастания wlog.
- Нам нужно найти k-е наименьшее число из числа m * n (это утверждение проблемы)
- m * n >= k, возвращает исключение null/raise в противном случае
Поддерживает максимальную кучу размера 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)) times = O (k * log (k))
Ответ 5
Существует фактически O (n) алгоритм деления и покорения, который решает проблему выбора в отсортированной матрице (т.е. нахождение k-го наименьшего элемента в отсортированной матрице).
Авторы Выбор в X + Y и матрицы с отсортированными строками и столбцами первоначально предлагали такой алгоритм, но способ, которым он работает, не это интуитивно понятно. Более простой алгоритм, представленный ниже, можно найти в Выбор в отсортированной матрице.
Определения. Предполагая отсортированную nxm-матрицу M с n <= m и без дубликатов, мы можем определить подматрицу N такую, что N состоит из всех столбцов с нечетными номерами и последнего столбца M. Ранг элемента e в матрице M определяется как 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)
Conquer. Другими словами, если мы хотим найти элемент с рангом k в M, нам нужно будет только изучить в подматрице P из M, которая ограничена элементами a и b такие, что rank(N,a) = floor(k/2) и rank(N,b) = ceil(k/2) + n. Сколько элементов находится в этой подматрице? По предыдущему неравенству и предположению, что нет дубликатов, поэтому самое большее O (n). Поэтому нам просто нужно выбрать k - rank(N,a) -й элемент в P, и это можно сделать, переставив P в отсортированный массив в O (m), а затем выполнив алгоритм с линейным временем, например quickselect, чтобы найти фактический элемент. rank(M,a) может быть вычислен в O (m), начиная с наименьшего элемента в матрице и итерации по столбцам до тех пор, пока не будет найден элемент больше, чем a, а затем перейдем к следующей строке и перейдем к предыдущему столбцу, пока не найдем первый элемент должен быть больше а и т.д. Таким образом, побеждающая часть работает в O (m).
Разделить. Осталось только найти a и b такие, что rank(N,a) = k/2 и rank(N,b) = k/2 + n. Это, очевидно, можно сделать рекурсивно на N (размер которого делится на 2 относительно 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). В случае квадратной матрицы (это также nb также O (k), так как мы можем ограничить поиск матрицей kxk, содержащей первый k столбцов и строк).
В общем случае матрицы с дубликатами можно было бы пометить элементы матрицы номерами строк и столбцов.
Ответ 6
Давайте предположим массив с r строками и c столбцами. Индексы начинаются с 1..
UPDATE: извините, я забыл упомянуть, что сначала вам нужно преобразовать k для следующих ниже формул:
k = n - (k-1). Где n - общее количество элементов, то есть r * c.
Вы можете получить индекс строки наибольшего элемента k: ceil (k/r)
Вы можете получить индекс столбца наибольшего элемента k: k% c (% - оператор Mod)
UPDATE:, если 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-й наибольший элемент.
Ответ 7
Подход:
- Дублируйте каждый node и вставьте его справа от оригинала node.
- Дублировать случайный указатель.
- Дублировать левый указатель.
- Отделите оба дерева.
Для графического объяснения обратитесь http://mytechspaze.com/index.php/2016/09/15/clone-binary-tree/