Dada una matriz de ansiedad donde cada una de las filas y columnas están ordenadas en orden ascendente, encuentre el k-ésimo elemento más pequeño en la matriz.
Tenga en cuenta que es el k-ésimo elemento más pequeño en el orden ordenado, no el k-ésimo elemento distinto.
Ejemplo:
matrix = [ [ 1, 5, 9], [10, 11, 13], [12, 13, 15] ],
k = 8,
volver 13.
Solución Java
Este problema es similar a Buscar una matriz 2D II. El punto de inicio de dicha matriz ordenada es la esquina inferior izquierda.
public int kthSmallest(int[][] matrix, int k) { int m=matrix.length; int lower = matrix[0][0]; int upper = matrix[m-1][m-1]; while(lower<upper){ int mid = lower + ((upper-lower)>>1); int count = count(matrix, mid); if(count<k){ lower=mid+1; }else{ upper=mid; } } return upper; } private int count(int[][] matrix, int target){ int m=matrix.length; int i=m-1; int j=0; int count = 0; while(i>=0&&j<m){ if(matrix[i][j]<=target){ count += i+1; j++; }else{ i--; } } return count; } |
