Trova x i numeri interi più piccoli in un elenco di lunghezza n

Question

Hai una lista di n interi e vuoi la x più piccola. Ad esempio,

x_smallest([1, 2, 5, 4, 3], 3) deve restituire [1, 2, 3].

Voterò su runtime unici all'interno della ragione e assegnerò il controllo verde al miglior runtime.

Inizierò con O(n * x): creare un array di lunghezza x. Scorrere la lista x volte, ogni volta tirando fuori il numero più piccolo successivo.

modifiche

• non avete idea di quanto grande o piccolo questi numeri sono davanti a tempo.
• Non ti interessa l'ordine finale, vuoi solo la x più piccola.
• Questo è già stato gestito in alcune soluzioni, ma diciamo che anche se non è garantito un elenco univoco, non si otterrà neanche un elenco degenerato come [1, 1, 1, 1, 1].

Answer 1

È possibile trovare il più piccolo elemento k-esimo in O (n) tempo. This has been discussed on StackOverflow before. Esistono algoritmi randomizzati relativamente semplici, come QuickSelect, che vengono eseguiti in tempo O (n) e algoritmi più complicati eseguiti in tempo O (n) nel caso peggiore.

Dato l'elemento k-esimo più piccolo è possibile effettuare un passaggio sull'elenco per trovare tutti gli elementi inferiori al k-esimo più piccolo e il gioco è fatto. (Suppongo che l'array di risultati non debba essere ordinato.)

Il tempo di esecuzione complessivo è O (n).

Answer 2

Aggiungi tutti i numeri in un heap ed elimina x di essi. La complessità è O((n + x) log n). Poiché x è ovviamente minore di n, è O(n log n).

Answer 3

Psudocode:

def x_smallest(array<int> arr, int limit) 
    array<int> ret = new array[limit] 

    ret = {INT_MAX} 

    for i in arr 
     for j in range(0..limit) 
      if (i < ret[j]) 
       ret[j] = i 
      endif 
     endfor 
    endfor 

    return ret 
enddef 

Answer 4

In pseudo-codice:

y = length of list/2 

if (x > y) 
    iterate and pop off the (length - x) largest 
else 
    iterate and pop off the x smallest 

O (n/2 * x)?

Answer 5

sort array 
slice array 0 x 

Scegliere il miglior algoritmo di ordinamento e il gioco è fatto: http://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms

Answer 6

gestire l'elenco delle x più alto finora in modo ordinato in una skip list. Scorrere l'array. Per ogni elemento, trova dove verrà inserito nell'elenco skip (tempo x log). Se all'interno della lista, è una delle x più piccole finora, quindi inseriscila e rimuovi l'elemento alla fine dell'elenco. Altrimenti non fare nulla.

Tempo O (n * log (x))

realizzazione alternativa: mantenere la collezione di x più alto finora in un max-heap, confrontare ogni nuovo elemento con elemento superiore del mucchio, e pop + inserto nuovo elemento solo se il nuovo elemento è inferiore all'elemento superiore. Poiché il confronto con l'elemento superiore è O (1) e pop/insert O (log x), questo è anche O (nlog (x))

Answer 7

Se l'intervallo di numeri (L) è noto, è possibile eseguire una modifica conteggio sort.

given L, x, input[] 
counts <- array[0..L] 
for each number in input 
    increment counts[number] 
next 

#populate the output 
index <- 0 
xIndex <- 0 
while xIndex < x and index <= L 
    if counts[index] > 0 then 
     decrement counts[index] 
     output[xIndex] = index 
     increment xIndex 
    else 
     increment index 
    end if 
loop 

Questo ha un tempo di esecuzione di O (n + L) (con sovraccarico di memoria di O (L)) che lo rende piuttosto interessante se il campo è piccolo (L < n log n).

Answer 8

È possibile ordinare quindi prendere i primi valori x?

Java: con QuickSort O (n log n)

import java.util.Arrays; 
import java.util.Random; 

public class Main { 

    public static void main(String[] args) { 
     Random random = new Random(); // Random number generator 
     int[] list = new int[1000]; 
     int lenght = 3; 

     // Initialize array with positive random values 
     for (int i = 0; i < list.length; i++) { 
      list[i] = Math.abs(random.nextInt()); 
     } 

     // Solution 
     int[] output = findSmallest(list, lenght); 

     // Display Results 
     for(int x : output) 
      System.out.println(x); 
    } 

    private static int[] findSmallest(int[] list, int lenght) { 
     // A tuned quicksort 
     Arrays.sort(list); 
     // Send back correct lenght 
     return Arrays.copyOf(list, lenght);  
    } 

} 

La sua piuttosto veloce.

Answer 9

private static int[] x_smallest(int[] input, int x) 
    { 
     int[] output = new int[x]; 
     for (int i = 0; i < x; i++) { // O(x) 
      output[i] = input[i]; 
     } 

     for (int i = x; i < input.Length; i++) { // + O(n-x) 
      int current = input[i]; 
      int temp; 

      for (int j = 0; j < output.Length; j++) { // * O(x) 
       if (current < output[j]) { 
        temp = output[j]; 
        output[j] = current; 
        current = temp; 
       } 
      } 
     } 

     return output; 
    } 

Guardando la complessità: O (x + (NX) * x) - supponendo che x è una costante, O (n)

Answer 10

def x_smallest(items, x): 
    result = sorted(items[:x]) 
    for i in items[x:]: 
     if i < result[-1]: 
      result[-1] = i 
      j = x - 1 
      while j > 0 and result[j] < result[j-1]: 
       result[j-1], result[j] = result[j], result[j-1] 
       j -= 1 
    return result 

caso peggiore è O (x * n), ma sarà in genere più vicino a O (n).

Answer 11

Che ne è dell'utilizzo di splay tree? Grazie all'esclusivo approccio dello splay tree al bilanciamento adattivo, consente un'implementazione rapida dell'algoritmo con l'ulteriore vantaggio di essere in grado di enumerare gli articoli x in ordine successivo. Ecco alcuni psuedocode.

public SplayTree GetSmallest(int[] array, int x) 
{ 
    var tree = new SplayTree(); 
    for (int i = 0; i < array.Length; i++) 
    { 
    int max = tree.GetLargest(); 
    if (array[i] < max || tree.Count < x) 
    { 
     if (tree.Count >= x) 
     { 
     tree.Remove(max); 
     } 
     tree.Add(array[i]); 
    } 
    } 
    return tree; 
} 

I GetLargest e Remove operazioni hanno una complessità ammortizzato di O (log (n)), ma perché l'ultimo elemento accede bolle all'inizio sarebbe normalmente O (1). Quindi la complessità dello spazio è O (x) e la complessità del tempo di esecuzione è O (n * log (x)). Se la matrice dovesse già essere ordinata, questo algoritmo otterrebbe la sua migliore complessità del caso di O (n) con una matrice ordinata crescente o decrescente. Tuttavia, un ordinamento molto strano o peculiare potrebbe comportare una complessità O (n^2). Riuscite a indovinare come dovrebbe essere ordinato l'array affinché ciò accada?

Answer 12

a Scala, e probabilmente altri linguaggi funzionali, una bazzecola:

scala> List (1, 3, 6, 4, 5, 1, 2, 9, 4) sortWith (_<_) take 5 
res18: List[Int] = List(1, 1, 2, 3, 4)