Не совсем ясно, как следует обрабатывать несколько дубликатов или что вы точно спрашиваете, , но я предполагаю, что вы хотите убедиться, что пространство O (1) удовлетворяется, независимо от сложности времени, вот что я попытаюсь ответить.
С массивами, O (1) пробел, O (N ^ 2) время:
Вы можете сделать это на месте, просто поменяв дублирующие элементы до конца. Вы можете найти дубликаты элементов, сохранив «текущий» указатель и просто проверив, что «следующий» элемент не совпадает с «текущим». Это время O (n ^ 2) в худшем случае. Пример:
[1,1,2,3,4,4,5] # "cur" is index 0 (element 1), and "next" is index 1 (element 1). Swap "next" to end.
[1,2,1,3,4,4,5] # swapping
[1,2,3,1,4,4,5] # swapping
... # Tedious swapping
[1,2,3,4,4,5,1] # Done swapping. Increment "cur".
[1,2,3,4,4,5,1] # "cur" is index 1 (element 2), and "next" is index 2 (element 3). Increment "cur"
... # Boring (no duplicates detected)
[1,2,3,4,4,5,1] # "cur" is index 3 (element 4), and "next" is index 4 (element 4). Swap "next" to end.
[1,2,3,4,5,4,1] # swapping
[1,2,3,4,5,1,4] # Done swapping. Increment "cur"
... # No more duplicates
# Done
Кроме того, на практике тратить время на меньшее пространство обычно не стоит. Память дешева, но медленное время отклика может потерять пользователей, что дорого. Заметным исключением являются встроенные системы, в которых память может быть ограничена, а входы короткими (для небольших входов асимптотическое время выполнения не имеет значения).
Со связанными списками, O (1) пробел, O (N) время:
Если бы у вас был связанный список вместо массива, вы могли бы сделать это за O (n) время и пространство O (1) довольно просто. Связанные списки имеют преимущество перед массивами, когда вы вынужден «сдвигать» элементы вокруг, так как они могут перемещать указатели вместо перемещения ВСЕХ элементов по позиции Стратегия cur / next аналогична для связанных списков, как указано выше с массивом. Вот пример:
1->1->2->3->4->4->5 # "cur" is first element (value 1), and "next" is second element (value 1). Swap "next" to the end.
1
\
1->2->3->4->4->5 # Move "cur"'s pointer to "next"'s next element.
1->2->3->4->4->5->1 # Set "next"'s pointer to null, set tails pointer to "next"
... # Boring stuff with no duplicates
1->2->3->4->4->5->1 # "cur" is fourth element (value 4), and "next" is fifth element (value 4). Swap fifth element to end.
4
\
1->2->3->4->5->1 # Move "cur"'s pointer to "next"'s next element.
1->2->3->4->5->1->4 # Set "next"'s pointer to null, set tails pointer to "next"
... # No more duplicates
# Done (hopefully it's clear moving and element to the end is O(1) instead of O(n))
Если вы можете превратить массив в связанный список за время O (n) и пространство O (1), проблема решена. Однако это невозможно. Связанные списки занимают больше места на элемент, чем массив, так что просто имея связанный список где-либо в программе, я думаю, что пространство O (1) будет быть нарушенным.
Так как это был вопрос для интервью, возможно, стоило бы отметить, что связанные списки несколько лучше для эффективного решения этой проблемы, независимо от формулировки проблемы. Обычно интервьюерам нравится видеть, что вы можете правильно применять структуры данных, и иногда они поддаются изменению типа ввода.
Умные структуры данных и тупой код работают намного лучше, чем другие
наоборот. --Eric S Raymond