Ricerca ottimale per k valori minimi nell'elenco non ordinato di numeri interi

Question

Sono stato appena intervistato con una domanda e sono curioso di sapere quale dovrebbe essere la risposta. Il problema era essenzialmente:

Supponiamo di avere un elenco non ordinato di n interi. Come trovi i valori minimi di k in questa lista? Cioè, se hai una lista di [10, 11, 24, 12, 13] e stai cercando i 2 valori minimi, otterrai [10, 11].

Ho una soluzione O (n * log (k)), e quella è la cosa migliore, ma sono curioso di ciò che le altre persone escogitano. Mi asterrò dall'inquinare i cervelli della gente pubblicando la mia soluzione e la modificherò tra un po '.

EDIT # 1: per esempio, una funzione simile: getMinVals lista (& l, int k)

EDIT # 2: Sembra che si tratta di un algoritmo di selezione, quindi mi lancio nella mia soluzione anche; iterando sull'elenco e utilizzando una coda di priorità per salvare i valori minimi. La specifica sulla coda di priorità era che i valori massimi sarebbero finiti nella parte superiore della coda di priorità, quindi confrontando la parte superiore a un elemento, la parte superiore sarebbe stata spuntata e l'elemento più piccolo sarebbe stato premuto. Ciò presupponeva che la coda di priorità avesse un push O (log n) e un pop O (1).

Answer 1

Questo è l'algoritmo quickSelect. È fondamentalmente un tipo rapido in cui si recita solo per una parte dell'array. Ecco una semplice implementazione in Python, scritta per brevità e leggibilità piuttosto che efficienza.

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) 

Questo verrà eseguito in O (N) in media, in quanto ad ogni iterazione, ci si aspetta di ridurre le dimensioni di data per una costante moltiplicativa. Il risultato non sarà ordinato. Il caso peggiore è O (N^2), ma questo è trattato essenzialmente allo stesso modo di un ordinamento rapido, usando cose come la mediana di-3.

Answer 2

Questo di solito è nei libri dell'algoritmo sotto selection algorithms o "selezione lineare". Ecco lo specifico section on min/max k values in a list. È O (nlog (k)).