Получить k-ые самые большие значения

Question

У меня есть некоторые проблемы. Я должен добавить много разных значений и просто получить только k-й по величине в конце. Как я могу эффективно реализовать это и какой алгоритм использовать?

Answer 1

Алгоритм:

1. Создать бинарную максимальную кучу, и добавить каждый из первых K значений в кучу.

2. Для каждого из оставшихся N-K значений, если она больше, чем последнее значение в куче:

   Поставил вместо последнего значения, и пузырек его для того, чтобы прибегать к куче.

3. Извлеките все значения (K) из кучи в список.

---

Сложность:

1. O(K)

2. O((N-K)×log(K))

3. O(K×log(K))

Если N-K ≥ K, то общая сложность O((N-K)×log(K)).

Если N-K < K, то общая сложность O(K×log(K)).

Answer 2

(на основе комментариев, которые вы не хотите, чтобы хранить все номера, вы видели ...)

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

Answer 3

Сначала постройте max-heap, используя те элементы, которые являются O (n) временем. затем извлеките k-1 элементов в O (klogn).