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

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

5 голосов
/ 18 февраля 2009

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

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

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

РЕДАКТИРОВАТЬ # 1: Например, такая функция, как: list getMinVals (list & l, int k)

РЕДАКТИРОВАТЬ # 2: похоже, что это алгоритм выбора, поэтому я также добавлю свое решение; перебирая список и используя приоритетную очередь для сохранения минимальных значений. Спецификация очереди с приоритетами заключалась в том, что максимальные значения будут находиться в верхней части очереди с приоритетами, поэтому при сравнении вершины с элементом верх будет выталкиваться, а элемент меньшего размера выдвигаться. Предполагалось, что приоритетная очередь имеет O (log n) push и O (1) pop.

Ответы [ 2 ]

6 голосов
/ 18 февраля 2009

Это алгоритм 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), но по сути это происходит так же, как быстрая сортировка с использованием таких вещей, как median-of-3.

4 голосов
/ 18 февраля 2009

Обычно это в книгах алгоритмов под алгоритмами выбора или "линейным выбором". Вот конкретный раздел о минимальных / максимальных значениях k в списке . Это O (nlog (k)).

...