Muy buenas, les saluda Luis y para hoy les traigo otro post.
Si se está entrevistando activamente con empresas, este es probablemente uno de los problemas más comunes que existen.
Si se está entrevistando activamente con empresas, este es probablemente uno de los problemas más comunes que existen.
Probablemente pueda encontrar este problema en leetcode, hackerrank y otros sitios web con preparación para entrevistas.
Muy bien, sé que probablemente ni siquiera entiendes por qué la ordenación rápida entra en esta imagen, pero te lo explicaré en un minuto.
Entonces, ¿qué queremos decir con encontrar el k-ésimo elemento más grande / más pequeño en la matriz?
Significa que con una matriz dada (ordenada o sin clasificar) quiero encontrar el primer o segundo elemento más grande / más pequeño en la matriz, si k es 1 o 2.
Por ejemplo, digamos que hay una matriz con los siguientes valores: [5,4,7,1,2,3,6]. Si k es 2, obtendré el valor de 2 porque es el segundo elemento más pequeño. Habría sido 6 si hubiera obtenido el segundo elemento más grande.
Generalmente, hay algunas formas de resolver esto:
- Ordene la matriz y devuelva el elemento indicándola a través de
k (arr[k]) - Usando el montón
mínimo / máximopara encontrar elk-ésimoelemento - Usando selección rápida / clasificación rápida parcial para resolver el problema.
Comencemos usando una matriz predeterminada para resolver el problema:
const getKthSmallest = (arr, k) => {
arr.sort(arr);
return arr[k - 1];
}
const arr = [8,2,3,4,1,7];
console.log(getKthSmallest(arr,5)); //will return 7
A primera vista, ordenar la función y luego indicar la respuesta parece simple. Sin embargo, esta no será una pregunta tan común en las entrevistas si eso es todo lo que se necesita para resolver.
En cuanto a la complejidad del rendimiento, este problema será o (n log n) porque Arrays.sort es esencialmente o (n log n). El valor devuelto es o (1).
La complejidad del espacio realmente puede depender de su implementación. Si solo está intercambiando todos sus elementos hacia una matriz ordenada, es o (1). Si está devolviendo una nueva matriz ordenada mediante la creación de una nueva matriz, entonces será o (n).
La tercera solución, la selección rápida, también es una buena solución para resolver este problema.
Para comprender la selección rápida, debemos comprender cómo funciona la ordenación rápida.
La ordenación rápida se realiza a través de la partición, que en cada partición divide una matriz en dos mitades: una mitad con valores menores que el pivote, otra mitad con valores mayores que el pivote.
El pivote se colocará en el índice de la derecha, y el índice indicará cuántos elementos más es mayor también.
Aquí está la implementación de quicksort:
const quickSort = (arr, low, high) => {
if(low < high) {
const border = partition(arr, low, high);
quickSort(arr, low, border - 1);
quickSort(arr, border + 1, high);
}
}
const arr = [3, 5, 1, 2, 4, 7, 6];
quickSort(arr, 0, arr.length - 1);
const partition = (array, low, high) => {
const pivot = array[high];
let i = low - 1;
let temp;
for(let j = low; j< high; j++){
if(pivot > array[j]){
i++;
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
temp = array[i + 1];
array[i + 1] = array[high];
array[high] = temp;
return i + 1;
}
De acuerdo … ¿cómo nos ayuda eso a resolver el k-ésimo problema más pequeño o más grande? Digamos que queremos el segundo elemento más pequeño de la matriz.
Dado que pivot nos dice cuántos elementos más son mayores / menores que el pivote mismo, también nos dice dónde se encuentra el k-ésimo elemento.
En otras palabras, si el pivote (es un índice, solo como recordatorio) es igual a k, entonces arr[k] será el k-ésimo elemento más pequeño / más grande de arr.
De lo contrario, si el pivote es menor que k es, entonces necesitamos dividir en las segundas mitades de la matriz, ya que el k-ésimo elemento se encuentra en la segunda parte de la submatriz.
Por otro lado, si el pivote es mayor que k, entonces necesitamos encontrar el k-ésimo elemento en el lado izquierdo de la matriz para nuestra respuesta.
Aquí hay una implementación de selección rápida:
const kthSmallest = (arr, low, high, k) {
const border = partition(arr, low, high);
if(border == k){
return arr[k];
}else if(border < k) {
return kthSmallest(arr, border + 1, high, k);
}else if(border > k) {
return kthSmallest(arr, low, border - 1, k);
}
return -1;
}
const partition = (array, low, high) => {
const pivot = array[high];
let i = low - 1;
let temp;
for(let j = low; j< array.length; j++){
if(pivot > array[j]){
i++;
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
temp = array[i + 1];
array[i + 1] = array[high];
array[high] = temp;
return i + 1;
}
Nuevamente, intente implementar esto sin mi guía aquí por su cuenta. Eso ayudará a comprender y cómo resolver el problema aún mejor.
Buena suerte. Gracias por leer este post.
Añadir comentario