Дан массив [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).

Здравствуйте, PaulMinelly, Вы писали:

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

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

Ещё другой странный вопрос. А если у меня не найдётся k разных чисел в массиве, то что делаем?

В любом случае, если мы типа фиксируем k и увеличиваем только N, то тогда O( N ), то можно, IMHO, решать "в лоб", так как k -- константа...

Если известно, что k<<N, то куча вполне подойдет (Ее можно создать линейно).

Еще ты не указал, важно ли выдавать результат отсортированным.

PM>Надо найти k-первых максимальных (и уникальных) чисел в массиве (k<N).

Нужно использовать поделенный на куски битовый вектор. Пусть у нас всего возможных значений чисел 2^32. Мы берем и делим эти значения на 2^16 групп по 2^16 значений. Из этих групп держим в памяти те, которые содержать k самых больших чисел. А если k мало, то можно хранить k групп с самыми большими значениями и не париться. Время: O(N). Недостатки: не имеет смысла использовать при больших k. В последнем случае можно воспользоваться поразрядной сортировкой.

Здравствуйте, PaulMinelly, Вы писали:

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

PM>Какие еще могут быть идеи за O(n) и память O(1).
одно максимальное находится за O(n), заменяем его за O(n) на минимальное и так к раз. K<<N значит K=O(1).
Можно конечно и побыстрей только это циклы писать, алгоритмами СТЛ не получится

Здравствуйте, PaulMinelly, Вы писали:

PM>Какие еще могут быть идеи за O(n) и память O(1).
Загнать данные в Judy array и взять k старших

E>Такой, намного странный вопрос, если я положу k == N, то что мы одидаем? Отсортированный за O(N) массив?

Нет, сортировать выходной массив не надо. Просто вывести k-максимальных чисел как получится, без сортировки. Иначе, действительно получилась бы сортировка за O(n).

Здравствуйте, Pro100Oleh, Вы писали:


PO>Еще ты не указал, важно ли выдавать результат отсортированным.

Нет, это не нужно. Результат всегда можно отсортировать при желании одним из 20 алгоритмов сортировки, но это уже будет другая задача. Не нужно это. Надо просто только вывести k-максимальных чисел как получится, в любом порядке.

PO>Если известно, что k<<N, то куча вполне подойдет (Ее можно создать линейно).

Да, k намного меньше чем N.
Как создать кучу линейно? В том же самом массиве? Извлечение из кучи одного элемента будет O(logk) а всех элементов O(klogk) хотя вроде нормально.

Здравствуйте, PaulMinelly, Вы писали:

[SKIPPED]

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

Только RadixSort O(N) по времени + избавится от дубликатов очень просто.
Существуют версии RadixSort сортирующие на месте, а counting можно делать битами, поэтому потребуется совсем чуть дополнительной пямяти, причем O(1)

Здравствуйте, PaulMinelly, Вы писали:

PM>Да, k намного меньше чем N.
PM>Как создать кучу линейно? В том же самом массиве? Извлечение из кучи одного элемента будет O(logk) а всех элементов O(klogk) хотя вроде нормально.
При k << N я думаю тебе должно подойти лобовое решение за O(N * k).
Находишь первое максимальное число за O(N). Запоминаешь его в список. Дальше ищешь за O(N) максимальное число, игнорируя значения массива из списка найденных значений.

Здравствуйте, vb-develop, Вы писали:

VD>Здравствуйте, PaulMinelly, Вы писали:

PM>>Да, k намного меньше чем N.
PM>>Как создать кучу линейно? В том же самом массиве? Извлечение из кучи одного элемента будет O(logk) а всех элементов O(klogk) хотя вроде нормально.
VD>При k << N я думаю тебе должно подойти лобовое решение за O(N * k).
VD>Находишь первое максимальное число за O(N). Запоминаешь его в список. Дальше ищешь за O(N) максимальное число, игнорируя значения массива из списка найденных значений.
Небольшое дополнение. После каждого прохода по всему массиву можно максимальное значение заменять на MAX_INT, и при этом игнорировать значения MAX_INT начиная со второго прохода.

Здравствуйте, vb-develop, Вы писали:

VD>Здравствуйте, vb-develop, Вы писали:

VD>>Здравствуйте, PaulMinelly, Вы писали:

PM>>>Да, k намного меньше чем N.
PM>>>Как создать кучу линейно? В том же самом массиве? Извлечение из кучи одного элемента будет O(logk) а всех элементов O(klogk) хотя вроде нормально.
VD>>При k << N я думаю тебе должно подойти лобовое решение за O(N * k).
VD>>Находишь первое максимальное число за O(N). Запоминаешь его в список. Дальше ищешь за O(N) максимальное число, игнорируя значения массива из списка найденных значений.
VD>Небольшое дополнение. После каждого прохода по всему массиву можно максимальное значение заменять на MAX_INT, и при этом игнорировать значения MAX_INT начиная со второго прохода.

Это решение теоритически не самое крутое. Но все равно спасибо.

Здравствуйте, PaulMinelly, Вы писали:



а где тут этюд?!
более подходящий форум имхо — алгритмы

Здравствуйте, PaulMinelly, Вы писали:

PM>2. Heapsort — тоже самое еще хуже.
PM>Составляем max-heapsort что называется in-place переставлением элементов в массиве и просеиванием вверх.
PM>Уже O(nlogn). Плюс вывод первых максимальных чисел O(klogn) — не интересно.

Э, почему nlogn?
Создаём приоритетную очередь с минимумом в голове, длиной не более k.
Скармливаем туда массив; при переполнении выбрасываем голову. Это nlogk в чистом виде.

Причём замечу, что можно очередь сделать на пирамиде, а можно на балансируемом двоичном дереве (только это уже не inplace).
В последнем случае мы очень просто поборемся с дубликатами.

set<int> stats;
for(it=begin; it!=end; ++it)
{
    stats.insert(*it);
    if(stats.size()==k+1)
        stats.erase(stats.begin());
}

DB>Здравствуйте, PaulMinelly, Вы писали:

DB>а где тут этюд?!
DB>более подходящий форум имхо — алгритмы

Да, этюда нет, надо бы передвинуть в алгоритмы. Не туда нажал, сорри

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, PaulMinelly, Вы писали:

PM>>2. Heapsort — тоже самое еще хуже.
PM>>Составляем max-heapsort что называется in-place переставлением элементов в массиве и просеиванием вверх.
PM>>Уже O(nlogn). Плюс вывод первых максимальных чисел O(klogn) — не интересно.

К>Э, почему nlogn?
К>Создаём приоритетную очередь с минимумом в голове, длиной не более k.
К>Скармливаем туда массив; при переполнении выбрасываем голову. Это nlogk в чистом виде.

К>Причём замечу, что можно очередь сделать на пирамиде, а можно на балансируемом двоичном дереве (только это уже не inplace).

Клево! Только пара вопросов.
Если строить приоритетную очередь на пирамиде — это имеется ввиду на куче?
Кучу можно построить на дополнительном массиве размера k — все здорово.
Только не понятно как можно отбрасывать голову у кучи. Ведь тогда последний элемент ставить в голову и просеивать вниз что занимает logk. Получается что кол-во вставок будет n каждая вставка — это logk просеиваний в куче. И того мы имеем nlogk.
Я правильно все прикинул? Там же в куче можно бороться с дубликатами сразу же.

Здравствуйте, PaulMinelly, Вы писали:

PM>Клево! Только пара вопросов.
PM>Если строить приоритетную очередь на пирамиде — это имеется ввиду на куче?

По-русски эту структуру (binary heap) иногда называют пирамидой. А сортировку, соответственно, пирамидальной.

PM>Кучу можно построить на дополнительном массиве размера k — все здорово.

А зачем на дополнительном? Просто скармливаем первые k элементов массива, и на их месте по ходу скармливания вырастает куча.
С учётом отбрасывания дубликатов, её размер может быть меньше k, ну и ладно — главное, что не больше.

Хотя если исходный массив жалко портить — то пусть будет дополнительный.

PM>Только не понятно как можно отбрасывать голову у кучи. Ведь тогда последний элемент ставить в голову и просеивать вниз что занимает logk. Получается что кол-во вставок будет n каждая вставка — это logk просеиваний в куче. И того мы имеем nlogk.

Именно это я и имел в виду. Что nlogk, а не nlogn.

PM>Я правильно все прикинул? Там же в куче можно бороться с дубликатами сразу же.

А вот тут меня сомнения обуяли — можно ли в куче эффективно бороться с дубликатами. Ведь она не обеспечивает строгий порядок.
Вот смотри: начали строить кучу из серии a,b,c,d,e.

a
| \
b  c
|\  \
d e

Добавляем ещё одну d или e. В ветку b она не попадёт, поэтому про дубликаты мы не узнаем.

Здравствуйте, PaulMinelly, Вы писали:

DB>>а где тут этюд?!
DB>>более подходящий форум имхо — алгритмы

PM>Да, этюда нет, надо бы передвинуть в алгоритмы. Не туда нажал, сорри

Как раз этюд.
Дайте народу поразмять извилину.
Решений-то много.

Кстати, функциональщики могут попрововать на иммутабельных структурах с последовательным доступом.
А хаскельщики — слабо на ленивом массиве?

Здравствуйте, PaulMinelly, Вы писали:

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

top-heapsort (куча размера k):

занос в кучу — C
проход по массиву с занесением в кучу O(n)
расход памяти O(1)

после прохода в куче искомый ответ.

Здравствуйте, Аноним, Вы писали:

А>занос в кучу — C
А>проход по массиву с занесением в кучу O(n)
А>расход памяти O(1)

А>после прохода в куче искомый ответ.
Не совсем... у тебя будет ответ с дубликатами...

Кроме того, если уж ты считаешь, что k -- это константа, то можно и попроще.
Заводишь просто массив из k элементов, ну и заполняешь его по мере просмотра большого массива...
Тоже O(N) получается...