Si encuentras algún fallo en tu código o trabajo, recuerda probar siempre en un entorno de testing antes subir el código al proyecto final.
Solución:
En realidad, hay una forma de resolver este problema en O (n log d) complejidad del tiempo y O (1) complejidad espacial, sin modificar el array. Aquí norte representa la longitud de la array, mientras D es la longitud del rango de números que contiene.
La idea es realizar una búsqueda binaria del k-ésimo elemento más pequeño. Comience con lo = elemento mínimo y hi = elemento máximo. En cada paso, verifique cuántos elementos son más pequeños que mid y actualícelo en consecuencia. Aquí está el código Java para mi solución:
public int kthsmallest(final List a, int k)
Tenga en cuenta que esta solución también funciona para matrices con duplicados y / o números negativos.
Voy a asumir que es de solo lectura array es un requisito fuerte, e intente encontrar compensaciones que no lo violen en esta respuesta (por lo tanto, usar el algoritmo de selección no es una opción, ya que modifica el array)
Como nota al margen, de wikipedia, no se puede hacer en el espacio O (1) sin modificar el array:
La complejidad de espacio requerida de la selección se ve fácilmente como k + O (1) (o n – k si k> n / 2), y los algoritmos in situ pueden seleccionar con solo O (1) almacenamiento adicional … la complejidad del espacio se puede reducir a costa de obtener solo una respuesta aproximada, o una respuesta correcta con cierta probabilidad
Se puede hacer en O (k) espacio con O (nlogk) hora. En caso k es constante, es O(1) solución
La idea es mantener un montón de tamaño máximo k. Primero llénelo con el primero k elementos, y luego seguir iterando el array. Si algún elemento x es más pequeño que la parte superior del montón, saque la cabeza vieja e inserte x en lugar de.
Cuando haya terminado, la cabeza del montón es el kel elemento más pequeño.
En términos de notación O grande, se puede hacer en O(n) con O(k) espacio usando un nuevo array de tamaño 2k, cargue los elementos en trozos al array, y use el algoritmo de selección en este auxiliar array para encontrar el kth elemento. Deseche todos los elementos más grandes que el elemento k’th y repita para el siguiente fragmento (cargue más k elementos). La complejidad es O(k*n/k) = O(n)
Sin embargo, esto rara vez se usa y tiene constantes significativamente peores que la solución de montón, que se usa con bastante frecuencia.
Si realmente desea usar el espacio O (1), se puede usar una solución de fuerza bruta encontrando un mínimo k veces. Solo necesita recordar el antiguo mínimo, que es el espacio constante. Esta solucion es O(nk) tiempo con espacio O (1), que es significativamente menos eficiente que las alternativas, en términos de tiempo.