Найдите 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

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

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 2

Псудокод:

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