Trouver les x plus petits entiers dans une liste de longueur n

Question

Vous avez une liste de n entiers et vous voulez le plus petit x. Par exemple,

x_smallest([1, 2, 5, 4, 3], 3) doit renvoyer [1, 2, 3].

Je voterai pour des runtimes uniques dans des limites raisonnables et donnerai le chèque vert au meilleur temps d'exécution. Je vais commencer par O(n * x): Créer un tableau de longueur x. Itérer à travers la liste x fois, en tirant chaque fois le plus petit entier suivant.

Edits

• Vous ne savez pas comment grand ou petit, ces chiffres sont à l'avance.
• Vous ne vous souciez pas de la commande finale, vous voulez juste le plus petit x.
• Ceci est déjà géré dans certaines solutions, mais disons que même si une liste unique n'est pas garantie, vous n'obtiendrez pas non plus de liste dégénérée comme [1, 1, 1, 1, 1].

Answer 1

Vous pouvez trouver le plus petit élément k-ième O (n) l'heure. This has been discussed on StackOverflow before. Il existe des algorithmes randomisés relativement simples, tels que QuickSelect, qui s'exécutent en O (n) temps prévu et des algorithmes plus complexes qui s'exécutent en O (n) temps le plus défavorable.

Étant donné le k-ème élément le plus petit, vous pouvez faire un passage sur la liste pour trouver tous les éléments inférieurs au k-ème plus petit et vous avez terminé. (Je suppose que le tableau des résultats n'a pas besoin d'être trié.)

L'exécution globale est O (n).

Answer 2

Ajoutez tous les n numéros à un tas et supprimez x d'entre eux. La complexité est O((n + x) log n). Puisque x est évidemment inférieur à n, c'est 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

Dans le pseudo-code:

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 

choisir le meilleur algorithme de tri et vous avez terminé: http://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms

Answer 6

Tenir à jour la liste des x le plus élevé jusqu'à présent dans l'ordre de tri dans une liste de saut. Itérer à travers le tableau. Pour chaque élément, trouvez où il serait inséré dans la liste de saut (log x time). Si à l'intérieur de la liste, il s'agit de l'un des x les plus petits, insérez-le et supprimez l'élément à la fin de la liste. Sinon, ne faites rien.

temps O (n * log (x))

mise en œuvre alternative: maintenir la collection de x le plus élevé jusqu'à présent dans un maximum tas, comparer chaque nouvel élément avec élément supérieur du tas, et pop + insert nouvel élément uniquement si le nouvel élément est inférieur à l'élément supérieur. Puisque la comparaison à l'élément supérieur est O (1) et pop/insert O (log x), c'est aussi O (nlog (x))

Answer 7

Si la plage de nombres (L) est connue, vous pouvez faire une modification genre de comptage.

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 

Cela a une durée d'exécution de O (n + L) (avec des frais généraux de mémoire de O (L)) ce qui le rend très attractif si la plage est petite (L < n log n).

Answer 8

Vous pouvez trier puis prendre les premières valeurs x?

Java: avec 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);  
    } 

} 

Son assez rapide.

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; 
    } 

En regardant la complexité: O (x + (nx) * x) - en supposant x est une constante, 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 

Le pire cas est O (x * n), mais sera typiquement plus proche de O (n).

Answer 11

Qu'en est-il de l'utilisation d'un splay tree? En raison de l'approche unique de l'équilibrage adaptatif de l'arborescence splay, l'implémentation de l'algorithme est simple, avec l'avantage supplémentaire de pouvoir énumérer par la suite les éléments x. Voici un pseudo code.

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; 
} 

Les GetLargest et Remove opérations ont une complexité amortie de O (log (n)), mais parce que le dernier élément accessible des bulles vers le haut, il serait normalement O (1). La complexité de l'espace est donc O (x) et la complexité d'exécution est O (n * log (x)). Si le tableau arrive à être déjà commandé alors cet algorithme obtiendrait sa meilleure complexité de O (n) avec un tableau ordonné ascendant ou descendant. Cependant, un ordre très étrange ou particulier pourrait entraîner une complexité O (n^2). Pouvez-vous deviner comment le tableau devrait être commandé pour que cela se produise?

Answer 12

SCALA, et probablement d'autres langages fonctionnels, une évidence:

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