Búsqueda óptima de valores mínimos k en la lista de enteros no ordenados

Question

Me acaban de entrevistar con una pregunta, y tengo curiosidad por saber cuál debería ser la respuesta. El problema era, esencialmente:

Supongamos que tiene una lista desordenada de n enteros. ¿Cómo se encuentran los k valores mínimos en esta lista? Es decir, si tiene una lista de [10, 11, 24, 12, 13] y está buscando los 2 valores mínimos, obtendrá [10, 11].

Tengo una solución O (n * log (k)), y eso es lo mejor que puedo, pero me da curiosidad lo que otras personas traen. Me abstendré de contaminar el cerebro de gente publicando mi solución y la editaré dentro de un rato.

editar # 1: Por ejemplo, una función como: getMinVals lista (lista & l, int k)

editar # 2: Parece que se trata de un algoritmo de selección, así que voy a echar en mi solución también; iterar sobre la lista y usar una cola de prioridad para guardar los valores mínimos. La especificación en la cola de prioridad era que los valores máximos terminarían en la parte superior de la cola de prioridad, por lo que al comparar la parte superior con un elemento, la parte superior aparecería y el elemento más pequeño sería empujado. Esto asumió que la cola de prioridad tenía un O (log n) push y un O (1) pop.

Answer 1

Este es el algoritmo quickSelect. Básicamente es un tipo rápido en el que solo recursivas para una parte de la matriz. Aquí hay una implementación simple en Python, escrita para la brevedad y la legibilidad en lugar de la eficiencia.

def quickSelect(data, nLeast) : 
    pivot = data[-1] 
    less = [x for x in data if x <= pivot] 
    greater = [x for x in data if x > pivot] 
    less.append(pivot) 

    if len(less) < nLeast : 
     return less + quickSelect(greater, nLeast - len(less)) 
    elif len(less) == nLeast : 
     return less 
    else : 
     return quickSelect(less, nLeast) 

Esto ejecutará en O (N) en promedio, ya que en cada iteración, se espera para reducir el tamaño de data por una constante multiplicativa. El resultado no será ordenado. El peor caso es O (N^2), pero esto se trata esencialmente de la misma manera que un tipo rápido, usando cosas como la mediana de 3.

Answer 2

Esto es generalmente en los libros de algoritmo en selection algorithms o "selección lineal". Aquí está el específico section on min/max k values in a list. Es O (nlog (k)).