Оптимальный поиск минимальных значений k в несортированном списке целых чисел

Question

У меня был только вопрос с вопросом, и мне любопытно, каким должен быть ответ. Проблема была, по существу:

Скажем, у вас есть несортированный список из n целых чисел. Как вы находите k минимальных значений в этом списке? То есть, если у вас есть список [10, 11, 24, 12, 13] и вы ищете два минимальных значения, вы получите [10, 11].

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

EDIT # 1: Например, функция, как: список getMinVals (список & л, внутр к)

EDIT # 2: Похоже, это алгоритм выбора, так что я буду бросать в моем решении также; итерация по списку и использование очереди приоритетов для сохранения минимальных значений. Спецификация в очереди приоритетов заключалась в том, что максимальные значения заканчиваются в верхней части очереди приоритетов, поэтому при сравнении вершины с элементом верхняя часть будет выскользнуть, а меньший элемент будет нажат. Это предполагало, что очередь приоритетов имела O (log n) push и O (1) pop.

Answer 1

Это алгоритм quickSelect. Это в основном быстрый вид, где вы только рекурсируете для одной части массива. Вот простая реализация в Python, написанная для краткости и удобочитаемости, а не эффективности.

def quickSelect(data, nLeast) : 
    pivot = data[-1] 
    less = [x for x in data if x <= pivot] 
    greater = [x for x in data if x > pivot] 
    less.append(pivot) 

    if len(less) < nLeast : 
     return less + quickSelect(greater, nLeast - len(less)) 
    elif len(less) == nLeast : 
     return less 
    else : 
     return quickSelect(less, nLeast) 

Это будет работать в O (N) в среднем, так как на каждой итерации, вы, как ожидается, уменьшить размер data с помощью мультипликативной константы. Результат не будет отсортирован. В худшем случае O (N^2), но это рассматривается, по сути, так же, как и быстрая сортировка, используя такие вещи, как медиана 3.

Answer 2

Это, как правило, в книгах алгоритмов под номером selection algorithms или «линейный выбор». Вот конкретные section on min/max k values in a list. Это O (nlog (k)).