Вы можете сделать это в O (n) на любом языке, в основном как:
# Get min and max values O(n).
min = oldList[0]
max = oldList[0]
for i = 1 to oldList.size() - 1:
if oldList[i] < min:
min = oldList[i]
if oldList[i] > max:
max = oldList[i]
# Initialise boolean list O(n)
isInList = new boolean[max - min + 1]
for i = min to max:
isInList[i] = false
# Change booleans for values in old list O(n)
for i = 0 to oldList.size() - 1:
isInList[oldList[i] - min] = true
# Create new list from booleans O(n) (or O(1) based on integer range).
newList = []
for i = min to max:
if isInList[i - min]:
newList.append (i)
Я предполагаю, что append - это операция O (1), которой она должна быть, если только у разработчика нет мозгов. Таким образом, при k шагах каждого O (n) у вас все еще есть операция O (n).
Неважно, выполняются ли шаги явно в вашем коде или они выполняются под покровом языка. В противном случае вы могли бы утверждать, что C qsort была одной операцией, и теперь у вас есть Святой Грааль процедуры сортировки O (1): -)
Как многие люди обнаружили, вы часто можете обменять сложность пространства на сложность времени. Например, вышеприведенное работает только потому, что нам разрешено вводить переменные isInList и newList. Если это не было разрешено, следующим лучшим решением может быть сортировка списка (вероятно, не лучше O (n log n)) с последующей операцией O (n) (я думаю) для удаления дубликатов.
Крайний пример: вы можете использовать тот же метод лишних пробелов для сортировки произвольного числа 32-разрядных целых чисел (скажем, у каждого из них только 255 или менее дубликатов) за O (n) времени, при условии, что вы можете выделить около четырех миллиардов байт для хранения счетчиков .
Просто инициализируйте все счета до нуля и пробегайте каждую позицию в вашем списке, увеличивая количество на основе числа в этой позиции. Это O (n).
Затем начните с начала списка и пробежитесь по массиву count, поместив столько правильных значений в список. Это O (1), где 1 составляет около четырех миллиардов конечно, но все еще постоянное время: -)
Это также O (1) сложность пространства, но очень большая «1». Обычно компромиссы не настолько серьезны.