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

Question

У вас есть список из n целых чисел, и вы хотите x наименьшее. Например,

x_smallest([1, 2, 5, 4, 3], 3) должен вернуть [1, 2, 3].

Я проголосую за уникальное время выполнения в пределах разумного и предоставлю зеленую проверку наилучшему времени выполнения.

Я начну с O(n * x): создайте массив длиной x. Повторяйте список x раз, каждый раз вытягивая следующее наименьшее целое число.

редактирует

• Вы не представляете, насколько большие или маленькие эти числа опережают время.
• Вам не важен окончательный заказ, вам нужен только самый маленький x.
• Это уже обрабатывается в некоторых решениях, но допустим, что хотя вам не гарантирован уникальный список, вы также не получите вырожденный список, например [1, 1, 1, 1, 1].

Answer 1

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

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

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

Answer 2

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

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

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

Answer 3

Если диапазон чисел (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

Answer 4

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

Answer 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).

Answer 6

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

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

Answer 7

А как насчет использования дерева сплайнов ? Благодаря уникальному подходу Splay Tree к адаптивной балансировке, он обеспечивает плавную реализацию алгоритма с дополнительным преимуществом возможности перечислять элементы x по порядку. Вот некоторый псевдокод.

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). Можете ли вы угадать, как массив должен быть упорядочен для этого?

Answer 8

    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 + (nx) * x) - при условии, что x является некоторой константой, O (n)

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

}

Это довольно быстро.*

Answer 10

sort array
slice array 0 x

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