Дан (очень) большой массив целых чисел, необходимо отсортировать по частоте появления элемента в массиве.
Ограничения: постоянная память, сложность O(N log(N)).
Пример:
[ 1 3 1 ] -> [ 3 1 1 ] т.к. частота(3) = 1; частота(1) = 2
[ 7 1 1 0 ] -> [ 7 0 1 1 ]
[ 9 1 0 1 3 1 3 3 ] -> [ 9 0 1 1 3 3 3 ]
Ограничения: постоянная память, сложность O(N log(N)).
Пример:
[ 1 3 1 ] -> [ 3 1 1 ] т.к. частота(3) = 1; частота(1) = 2
[ 7 1 1 0 ] -> [ 7 0 1 1 ]
[ 9 1 0 1 3 1 3 3 ] -> [ 9 0 1 1 3 3 3 ]
5 комментариев:
Может быть так:
1. если массив содержит повторяющиеся числа, то память будет O(k), k < N, если это не так, то 2 степ не нужен
2. просто подсчитать частоту это O(N)
3. quick sort O(NlogN)
Тогда O(N) + O(NlogN) = O(NlogN) и память O(1).
1. память постоянная, т.е O(1)
2. частоту каждого элемента за O(N) ? как
Если мне не изменяет память, то это задача на внешную сортировку. Можно использовать сортировку слиянием, но сортировать надо по значению в хэш таблице, содержащую в качестве ключа значение из массива, а в качестве значения частоту. То есть:
1. Берем M/2 значений из массива и создаем хэш таблицу с частотой
2. Сортируем слиянием по частоте
3. Берем следующию партию M/2 и сливаем с первой
Где М - это ограничение памити. При М много меньше N, время на первоначальное создание таблицы частот нивилируется.
При выводе отсортированных данных необходимо генерить повторение значений по частоте.
Да, алгоритм получится не стабильным, но в условиях про стабильность ничего не сказано.
1. Сначала отсортируем обычным qsort'ом
2. Теперь идём по массиву, держа дополнительно переменную j (изначально j = 0) и смотрим на группы одинаковых, если группа состоит из одного числа (как 3 в примере), тут же выводим, если больше, то a[j] = кол-во чисел в группе, a[j + 1] = само число, j += 2.
Очевидно, что при этом действии массив не запортится, т.к. i будет >= j + 1. Очевидно также, что и j не уйдет за пределы, т.к. за каждое такое заполнение мы описываем не менее двух чисел
3. Делаем также обычную сортировку, но только сортируем массив как пары
4. Тупо выводим
P.S.: мир тесен, гуглила по "tomcat-7 ebuild", вышла на Ваш блог, а увидев жирный тег "задачка", не могла не пройти по нему :)
Отправить комментарий