Encuentra los x enteros más pequeños en una lista de longitud n

Question

Tienes una lista de n enteros y quieres la x más pequeña. Por ejemplo,

x_smallest([1, 2, 5, 4, 3], 3) debe devolver [1, 2, 3].

Voy a votar por tiempos de ejecución únicos dentro de lo razonable y otorgaré el chequeo verde al mejor tiempo de ejecución.

Comenzaré con O(n * x): crea una matriz de longitud x. Itere a través de la lista x veces, cada vez que extraiga el siguiente número entero más pequeño.

ediciones

• usted no tiene idea de lo grande o pequeño que estos números son antes de tiempo.
• No le importa la orden final, solo quiere la x más pequeña.
• Esto ya se está manejando en algunas soluciones, pero digamos que si bien no se garantiza una lista única, tampoco se obtendrá una lista degenerada como [1, 1, 1, 1, 1].

Answer 1

puede encontrar el elemento k-ésimo menor en O (n) tiempo This has been discussed on StackOverflow before. Existen algoritmos aleatorios relativamente simples, como QuickSelect, que se ejecutan en O (n) tiempo esperado y algoritmos más complicados que se ejecutan en O (n) tiempo del peor caso.

Dado el k-ésimo elemento más pequeño, puede hacer una pasada sobre la lista para encontrar todos los elementos menores que la k-ésima y habrá terminado. (Supongo que no es necesario ordenar el conjunto de resultados.)

El tiempo de ejecución general es O (n).

Answer 2

Agregue todos los n números a un montón y elimine x de ellos. La complejidad es O((n + x) log n). Como x es obviamente menor que n, es 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

En pseudo código:

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 

elegir el mejor algoritmo de ordenación y ya está: http://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms

Answer 6

mantener la lista de la x más alto hasta ahora en el orden establecido en un contenedor-lista. Itera a través de la matriz. Para cada elemento, encuentre dónde se insertará en la lista de omisiones (log x time). Si está en el interior de la lista, es una de las x más pequeñas hasta ahora, así que insértela y elimine el elemento al final de la lista. De lo contrario, no haga nada.

tiempo O (n * log (x))

implementación alternativa: mantener la colección de x más alto hasta ahora en un max-montón, comparar cada nuevo elemento con el elemento superior de la pila, y pop + inserto nuevo elemento solo si el nuevo elemento es menor que el elemento superior. Dado que la comparación con el elemento superior es O (1) y pop/insertar O (registro x), esto también es O (nlog (x))

Answer 7

Si se conoce el rango de números (L), puede hacer una modificación contando tipo.

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 

Esto tiene un tiempo de ejecución de O (n + L) (con sobrecarga de memoria de O (L)), que hace que sea muy atractivo si el rango es pequeño (L < n log n).

Answer 8

Puede ordenar y tomar los primeros x valores?

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

} 

Es bastante rápido.

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 cuanto a la complejidad: O (x + (nx) * x) - suponiendo que x es una 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 

Peor caso es O (x * n), pero normalmente estará más cerca de O (n).

Answer 11

¿Qué hay de usar un splay tree? Debido al enfoque único del árbol desplegable para el equilibrio adaptativo, hace una implementación ingeniosa del algoritmo con la ventaja adicional de poder enumerar los elementos x en orden posteriormente. Aquí hay un 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; 
} 

Los GetLargest y Remove operaciones tienen una complejidad amortizado de O (log (n)), pero debido a que el último elemento visitada burbujas a la parte superior normalmente sería O (1). Entonces, la complejidad del espacio es O (x) y la complejidad del tiempo de ejecución es O (n * log (x)). Si la matriz ya está ordenada, entonces este algoritmo obtendría la mejor complejidad de caso de O (n) con una matriz ordenada ascendente o descendente. Sin embargo, un orden muy extraño o peculiar podría dar como resultado una complejidad O (n^2). ¿Puedes adivinar cómo debería ordenarse la matriz para que eso suceda?

Answer 12

en Scala, y probablemente otros lenguajes funcionales, una obviedad:

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