Дан массив [1;n]
— содержащий n целых числел (32 битных integer);
— массив НЕ отсортирован;
— в массиве есть дубликаты;

Надо найти k-первых максимальных (и уникальных) чисел в массиве (k<N).
Т.е. в массиве {1,2,3,3,4} при k=3 ответ будет 2,3,4 а не 3,3,4.

Идеи:
1. Quicksort O(nlogn). Избавляемся от дубликатов O(n).
Время растет пропорционально O(nlogn) — не интересно.
2. Heapsort — тоже самое еще хуже.
Составляем max-heapsort что называется in-place переставлением элементов в массиве и просеиванием вверх.
Уже O(nlogn). Плюс вывод первых максимальных чисел O(klogn) — не интересно.
В инете читал разговоры про составление maxheap inplace за O(n) но не дошло пока (мало образования может кто сможет пояснить есть такое или нет?
Не понятно: как выкидывать дубликаты.
3. Counting sort используя bit-вектор — O(n) — уже интереснее.
Плюсы: Битвектор сожрет O(2^32/8) байт памяти или 536 мегов — что уже не интересно. Отпадает.
Плюс: отличная борьба с дубликатами за тот же самый проход.
4. Алгоритм поиска Хоара "Divide and Conquer" (тот что и про поиск медианы) — O(n) все круто, но отпадает.
Потому что он эффективен для поска k-первых максимальных/минимальных чисел в массиве с _уникальными_ числами. У нас же массив содержит дубликаты. Поэтому применив поиск k-первых максимальных чисел мы получим ответ с дубликатами, нам же надо без дубликатов. Отпадает?

Какие еще могут быть идеи за O(n) и память O(1).