Найти x наименьших целых чисел в списке длины n

Ответ 1

Вы можете найти k-й наименьший элемент в O (n) времени. fooobar.com/questions/34037/.... Существуют относительно простые рандомизированные алгоритмы, такие как QuickSelect, которые выполняются в ожидаемом времени O (n) и более сложных алгоритмах, которые выполняются в O (n) в худшем случае.

Учитывая k-й наименьший элемент, вы можете сделать один проход по списку, чтобы найти все элементы, меньшие k-го наименьшего, и вы закончили. (Я предполагаю, что массив результатов не нужно сортировать.)

Общее время выполнения - O (n).

Ответ 2

Сохранять список x, самый высокий до сих пор в отсортированном порядке в списке пропуска. Итерации через массив. Для каждого элемента найдите, где он будет вставлен в список пропуска (log x time). Если внутри списка, это один из самых маленьких x, поэтому вставьте его и удалите элемент в конце списка. В противном случае ничего не делать.

Время O (n * log (x))

Альтернативная реализация: поддерживайте коллекцию х наивысших до сих пор в макс-куче, сравните каждый новый элемент с верхним элементом кучи и поп + вставьте новый элемент только в том случае, если новый элемент меньше верхнего элемента. Поскольку сравнение с верхним элементом является O (1) и pop/insert O (log x), это также O (nlog (x))

Ответ 3

Добавьте все n чисел в кучу и удалите x из них. Сложность O((n + x) log n). Так как x, очевидно, меньше n, то O(n log n).

Ответ 4

Если диапазон чисел (L) известен, вы можете сделать модифицированную сортировку.

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

У этого есть время выполнения O (n + L) (с издержками памяти O (L)), что делает его довольно привлекательным, если диапазон мал (L < n log n).

Ответ 5

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

В худшем случае O (x * n), но обычно будет ближе к O (n).

Ответ 6

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

Ответ 7

В псевдокоде:

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)?

Ответ 8

sort array
slice array 0 x

Выберите лучший алгоритм сортировки, и все готово: http://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms

Ответ 9

Затем вы можете отсортировать первые значения x?

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

}

Его довольно быстро.

Ответ 10

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

Глядя на сложность:   O (x + (n-x) * x) - при условии, что x - некоторая константа, O (n)

Ответ 11

Как насчет использования splay tree? Из-за уникального подхода Splay Tree к адаптивной балансировке он обеспечивает слабую реализацию алгоритма с дополнительным преимуществом возможности перечисления элементов x в дальнейшем. Вот несколько 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;
}

Операции GetLargest и Remove имеют амортизированную сложность O (log (n)), но поскольку последний доступный элемент пузырится вверх, он обычно будет O (1). Таким образом, сложность пространства O (x), а сложность выполнения - O (n * log (x)). Если массив уже будет упорядочен, то этот алгоритм будет обеспечивать наилучшую сложность O (n) с любым восходящим или нисходящим упорядоченным массивом. Однако очень странное или своеобразное упорядочение может привести к сложности O (n ^ 2). Можете ли вы догадаться, как нужно было бы заказать массив для этого?

Ответ 12

В scala и, возможно, в других функциональных языках нет проблем:

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