esta es una pregunta de la entrevista de google:

Dada una matriz N * N. Todas las filas están ordenadas y todas las columnas están ordenadas. Encuentre el elemento Kth más grande de la matriz.

hacerlo en n ^ 2 es simple y podemos ordenarlo usando heap o merge sort (n lg n) y luego obtenerlo, pero ¿hay un mejor enfoque, mejor que (n lg n)?

ejemplo de la matriz ::

 1   5   7  12
 3   6   8  14
 4   9  10  15
11  17  19  20

1 <5 <7 <12 y 1 <3 <4 <11 de manera similar a las otras filas y columnas. ahora digamos que necesitamos encontrar el décimo elemento más pequeño, aquí es 11 ... espero que esto agregue algunos detalles a la pregunta ...