В зависимости от параметров вашей проблемы, существует множество подходов к решению этой проблемы.
Если вам не разрешено использовать O (n) внешнюю память , тогда одним из вариантов будетиспользовать стандартный алгоритм сортировки для сортировки массива за время O (n log n), затем выполнить второй проход над ним, чтобы переместить дубликаты в конец (как вы предложили).Код, который вы разместили выше, занимает O (n 2 ) времени, но я думаю, что этот шаг можно выполнить за O (n log n), используя немного более сложный алгоритм.Идея работает в два этапа.На первом этапе за время O (n log n) вы выводите все недублированные элементы на передний план в отсортированном порядке, а все дубликаты - на задний план в несортированном порядке.Сделав это, вы сортируете заднюю половину массива за O (n log n) времени, используя алгоритм сортировки с первого шага.
Я не собираюсь вдаваться в код длясортировать массив.Я действительно люблю сортировку, но есть так много других хороших ресурсов о том, как сортировать массивы на месте, что не стоит использовать мое время / пространство здесь, чтобы в них разбираться.Если это поможет, вот ссылки на реализации Java heapsort , quicksort и smoothsort , все из которых выполняются за O (n log n) времени.Heapsort и smoothsort используют только O (1) внешнюю память, в то время как quicksort может использовать O (n) в худшем случае (хотя хорошие реализации могут ограничить это O (log n), используя симпатичные трюки).
ИнтересныйКод - это логика для вывода всех недублированных элементов в начало диапазона.Интуитивно понятно, что код работает, сохраняя два указателя - указатель чтения и указатель записи.Указатель чтения указывает на следующий элемент для чтения, а указатель записи указывает на место, где должен быть размещен следующий уникальный элемент.Например, для этого массива:
1 1 1 1 2 2 3 4 5 5
Мы начинаем с указателей чтения и записи, изначально указывающих на 1:
write v
1 1 1 1 2 2 3 4 5 5
read ^
Далее мы пропускаем указатель чтения вперед до следующего элементаэто не 1. Это находит 2:
write v
1 1 1 1 2 2 3 4 5 5
read ^
Затем мы поднимаем указатель записи в следующее место:
write v
1 1 1 1 2 2 3 4 5 5
read ^
Теперь мы поменяем местами 2 на местопо указателю записи:
write v
1 2 1 1 1 2 3 4 5 5
read ^
передвиньте указатель чтения на следующее значение, которое не равно 2:
write v
1 2 1 1 1 2 3 4 5 5
read ^
, затем передвиньте указатель записи:
write v
1 2 1 1 1 2 3 4 5 5
read ^
Опять же, мы обмениваемся значениями, на которые указывают 'read' и 'write', и перемещаем указатель записи вперед, а затем перемещаем указатель чтения к следующему уникальному значению:
write v
1 2 3 1 1 2 1 4 5 5
read ^
Еще раз получаем
write v
1 2 3 4 1 2 1 1 5 5
read ^
и последняя итерация дает
write v
1 2 3 4 5 2 1 1 1 5
read ^
Если мы теперь отсортируем указатель записи на указатель чтения, мы получим
write v
1 2 3 4 5 1 1 1 2 5
read ^
и бинго!У нас есть ответ, который мы ищем.
В (непроверенном, извините ...) Java-коде этот шаг исправления может выглядеть следующим образом:
int read = 0;
int write = 0;
while (read < array.length) {
/* Swap the values pointed at by read and write. */
int temp = array[write];
array[write] = array[read];
array[read] = temp;
/* Advance the read pointer forward to the next unique value. Since we
* moved the unique value to the write location, we compare values
* against array[write] instead of array[read].
*/
while (read < array.length && array[write] == array[read])
++ read;
/* Advance the write pointer. */
++ write;
}
Этот алгоритм выполняетсяза время O (n), что приводит к общему алгоритму задачи O (n log n).Поскольку на этапе переупорядочения используется память O (1), общее использование памяти будет равно либо O (1) (для чего-то вроде сглаживания или heapsort), либо O (log n) (для чего-то вроде быстрой сортировки).
РЕДАКТИРОВАТЬ: После разговора с другом, я думаю, что есть гораздо более элегантное решение проблемы, основанное на модификации быстрой сортировки.Как правило, когда вы запускаете быструю сортировку, вы в конечном итоге разбиваете массив на три области:
+----------------+----------------+----------------+
| values < pivot | values = pivot | values > pivot |
+----------------+----------------+----------------+
Затем рекурсия сортирует первую и последнюю области, чтобы расположить их в отсортированном порядке.Тем не менее, мы можем изменить это для нашей версии проблемы.В качестве примитива нам понадобится алгоритм вращение , который берет два соседних блока значений в массиве и обменивает их за O (n) раз.Это не меняет относительный порядок элементов в этих блоках.Например, мы могли бы использовать вращение для преобразования массива
1 2 3 4 5 6 7 8
в
3 4 5 6 7 8 1 2
и сделать это за O (n) раз.
Модифицированная версия быстрой сортировки будет работать с использованием алгоритма трехстороннего разделения Bentley-McIlroy (описано здесь ), чтобы, используя O (1) дополнительное пространство, переставить элементы массива в конфигурацию, показанную выше,Затем мы применяем вращение, чтобы изменить порядок элементов, чтобы они выглядели так:
+----------------+----------------+----------------+
| values < pivot | values > pivot | values = pivot |
+----------------+----------------+----------------+
Затем мы выполняем своп, чтобы мы переместили ровно одну копию элемента pivot в набор элементов как минимумстоль же большой как центр.Это может иметь дополнительные копии стержня позади.Затем мы рекурсивно применяем алгоритм сортировки к диапазонам <и>.Когда мы сделаем это, результирующий массив будет выглядеть так:
+---------+-------------+---------+-------------+---------+
| < pivot | dup < pivot | > pivot | dup > pivot | = pivot |
+---------+-------------+---------+-------------+---------+
Затем мы применяем два поворота к диапазону, чтобы поместить его в окончательный порядок.Во-первых, поверните дублирующиеся значения меньше, чем вокруг оси, со значениями больше, чем вокруг оси.Это дает
+---------+---------+-------------+-------------+---------+
| < pivot | > pivot | dup < pivot | dup > pivot | = pivot |
+---------+---------+-------------+-------------+---------+
. На этом этапе этот первый диапазон представляет собой уникальные элементы в порядке возрастания:
+---------------------+-------------+-------------+---------+
| sorted unique elems | dup < pivot | dup > pivot | = pivot |
+---------------------+-------------+-------------+---------+
Наконец, сделайте одно последнее вращение дублирующих элементов больше, чем шарнир, иэлементы, равные центру, чтобы привести это:
+---------------------+-------------+---------+-------------+
| sorted unique elems | dup < pivot | = pivot | dup > pivot |
+---------------------+-------------+---------+-------------+
Обратите внимание, что эти последние три блока - только отсортированные повторяющиеся значения:
+---------------------+-------------------------------------+
| sorted unique elems | sorted duplicate elements |
+---------------------+-------------------------------------+
и вуаля!У нас все в порядке, который мы хотим.Используя тот же анализ, который вы сделали бы для обычной быстрой сортировки, плюс тот факт, что мы выполняем только O (n) работу на каждом уровне (три дополнительных вращения), в лучшем случае это получается O (n log n)с использованием O (log n) памяти.Это все еще O (n 2 ) в худшем случае с O (log n) памятью, но это происходит с крайне низкой вероятностью.
Если вам разрешено использовать O (n) память, одним из вариантов будет построение сбалансированного бинарного дерева поиска из всех элементов, в которых хранятся пары ключ / значение, где каждый ключ является элементом массива, а значение - это число раз, которое оно появляется,Затем вы можете отсортировать массив в вашем формате следующим образом:
- Для каждого элемента в массиве:
- Если этот элемент уже существует в BST, увеличить его счетчик.
- В противном случае добавьте новый узел в BST с этим элементом, имеющим счет 1.
- Выполните обход BST по порядку.При обнаружении узла выведите его ключ.
- Выполните второй обход BST.При обнаружении узла, если он имеет число больше единицы, выведите n - 1 копию этого узла, где n - это число раз, когда он появляется.
Время выполнения этого алгоритма равно O (nвойти n), но было бы довольно сложно кодировать BST с нуля.Это также требует внешнего пространства, что я не уверен, что вам разрешено это делать.
Однако, если вам разрешено внешнее пространство и сортируемые массивы маленькие и содержат маленькие целые числа, вы можете изменитьПриведенный выше подход с использованием модифицированной сортирующей счет .Просто замените BST массивом, достаточно большим, чтобы каждое целое число в исходном массиве было ключом.Это сокращает время выполнения до O (n + k) с использованием памяти O (k), где k - самый большой элемент в массиве.
Надеюсь, это поможет!