arrays - initialize - multidimensional array javascript

Kth elemento más pequeño en matriz ordenada

Question

Esta es una pregunta de entrevista.

Encuentre el elemento más pequeño en una matriz con filas y columnas ordenadas.
¿Es correcto que el elemento más pequeño K ^th sea ​​uno de a[i, j] como i + j = K ?

Answer 1

Como la gente mencionó anteriormente, la forma más fácil es construir un min heap . Aquí hay una implementación de Java usando PriorityQueue:

private int kthSmallestUsingHeap(int[][] matrix, int k) {
int n = matrix.length;
// This is not necessary since this is the default Int comparator behavior
Comparator<Integer> comparator = new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o1 - o2;
}
};
// building a minHeap
PriorityQueue<Integer> pq = new PriorityQueue<>(n*n, comparator);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
pq.add(matrix[i][j]);
}
}
int ans = -1;
// remove the min element k times
for (int i = 0; i < k; i++) {
ans = pq.poll();
}
return ans;
}

Answer 2

Empiece a atravesar la matriz desde la esquina superior izquierda (0,0) y use un montón binario para almacenar la "frontera", un borde entre una parte visitada de la matriz y el resto.

Implementación en Java:

private static class Cell implements Comparable<Cell> {
private final int x;
private final int y;
private final int value;
public Cell(int x, int y, int value) {
this.x = x;
this.y = y;
this.value = value;
}
@Override
public int compareTo(Cell that) {
return this.value - that.value;
}
}
private static int findMin(int[][] matrix, int k) {
int min = matrix[0][0];
PriorityQueue<Cell> frontier = new PriorityQueue<>();
frontier.add(new Cell(0, 0, min));
while (k > 1) {
Cell poll = frontier.remove();
if (poll.y + 1 < matrix[poll.x].length) frontier.add(new Cell(poll.x, poll.y + 1, matrix[poll.x][poll.y + 1]));
if (poll.x + 1 < matrix.length) frontier.add(new Cell(poll.x + 1, poll.y, matrix[poll.x + 1][poll.y]));
if (poll.value > min) {
min = poll.value;
k--;
}
}
return min;
}

Answer 3

Falso.

Considera una matriz simple como esta:

1 3 5
2 4 6
7 8 9

9 es el elemento más grande (9º más pequeño). Pero 9 está en A [3, 3], y 3 + 3! = 9. (No importa qué convención de indexación utilice, no puede ser cierto).

Puede resolver este problema en tiempo O (k log n) combinando las filas de forma incremental, aumentadas con un montón para encontrar el elemento mínimo de manera eficiente.

Básicamente, usted pone los elementos de la primera columna en un montón y rastrea la fila de donde provienen. En cada paso, quita el elemento mínimo del montón y presiona el siguiente elemento de la fila de la que vino (si llega al final de la fila, entonces no empuja nada). Tanto eliminar el mínimo como agregar un nuevo elemento cuesta O (log n). En el paso j, se elimina el elemento j th más pequeño, por lo que después de k pasos, se realiza por un costo total de las operaciones O(k log n) (donde n es el número de filas en la matriz).

Para la matriz anterior, inicialmente comienza con 1,2,7 en el montón. Quita 1 y agrega 3 (ya que la primera fila es 1 3 5 ) para obtener 2,3,7 . Quitas 2 y sumas 4 para obtener 3,4,7 . Retire 3 y agregue 5 para obtener 4,5,7 . Quita 4 y agrega 6 para obtener 5,6,7 . Tenga en cuenta que estamos eliminando los elementos en el orden ordenado globalmente. Puede ver que continuar este proceso producirá el elemento k th más pequeño después de k iteraciones.

(Si la matriz tiene más filas que columnas, entonces opere en las columnas para reducir el tiempo de ejecución).

Answer 4

Kth elemento más pequeño en la matriz:

El problema se puede reducir de la siguiente manera.

si k es 20, entonces tome k * k matriz (donde la respuesta estará definitivamente).

Ahora puede fusionar las filas en par repetidamente para construir una matriz ordenada y luego encontrar el número más pequeño kth.

Answer 5

Parece que esto solo usa la función: cada fila está ordenada, pero no usa su función ordenada por columnas.

Answer 6

O(k log(k)) solución.

• Construye un minheap.

• Añadir (0,0) a la pila. Si bien, no hemos encontrado el kth elemento más pequeño, elimine el elemento superior (x,y) del montón y agregue los siguientes dos elementos [(x+1,y) y (x,y+1)] si no lo han hecho sido visitado antes

Estamos realizando operaciones O(k) en un montón de tamaño O(k) y, por lo tanto, la complejidad.

Answer 7

//int arr[][] = {{1, 5, 10, 14},
// {2, 7, 12, 16},
// {4, 10, 15, 20},
// {6, 13, 19, 22}
//};
// O(k) Solution
public static int myKthElement(int arr[][], int k) {
int lRow = 1;
int lCol = 0;
int rRow = 0;
int rCol = 1;
int count = 1;
int row = 0;
int col = 0;
if (k == 1) {
return arr[row][col];
}
int n = arr.length;
if (k > n * n) {
return -1;
}
while (count < k) {
count++;
if (arr[lRow][lCol] < arr[rRow][rCol]) {
row = lRow;
col = lCol;
if (lRow < n - 1) {
lRow++;
} else {
if (lCol < n - 1) {
lCol++;
}
if (rRow < n - 1) {
lRow = rRow + 1;
}
}
} else {
row = rRow;
col = rCol;
if (rCol < n - 1) {
rCol++;
} else {
if (rRow < n - 1) {
rRow++;
}
if (lCol < n - 1) {
rCol = lCol + 1;
}
}
}
}
return arr[row][col];
}