Предположим, у вас есть массив размером содержащий целые числа от до включительно, с ровно пятью повторениями. Мне нужно предложить алгоритм, который может найти повторяющиеся числа в времени. Я не могу ни о чем думать. Я думаю, что сортировка, в лучшем случае, будет ? Тогда при обходе массива будет , что приведет к . Тем не менее, я не уверен, что сортировка будет необходима, поскольку я видел некоторые хитрые вещи со связанным списком, очередями, стеками и т. Д.
algorithms
arrays
searching
darylnak
источник
источник
Ответы:
Вы можете создать дополнительный массивB размером n . Изначально установите все элементы массива на 0 . Затем переберите входной массив A и увеличьте B[A[i]] на 1 для каждого i . После этого вы просто проверяете массив B : цикл над A и если B [ A [ i ] ] > 1 то Я [ я ] повторяется. Вы решаете это в O ( n ) время за счет памяти, которая составляет O ( n ) и потому, что ваши целые числа находятся в диапазоне от 1 до п - 5 .
источник
Решение в ответе fade2black является стандартным, но использует пространствоO ( n ) . Вы можете улучшить это до O ( 1 ) пространство следующим образом:
Этот алгоритм предполагает модель машины ОЗУ, в которой базовые арифметические операции над -битными словами занимают O ( 1 ) времени.O(logn) O(1)
Другой способ сформулировать это решение заключается в следующем:
Это решение показывает, что если мы заменим 5 на , то получим (я полагаю) алгоритм O ( d 2 n ) , используя пространство O ( d 2 ) , которое выполняет O ( d n ) арифметические операции над целыми числами битовой длины O ( d log n ) , сохраняя не более O ( d ) из них в любой момент времени. (Это требует тщательного анализа умножений, которые мы выполняем, большинство из которых включает в себя один операнд длины только O ( log nd O ( д2н ) O ( д2) O (dн ) O (dжурналн ) O (d) .) Возможно, что это можно улучшить до O ( d n ) времени и O ( d ) пространства с помощью модульной арифметики.O (logн ) O (dн ) O (d)
источник
Существует также линейный алгоритм времени и постоянного пространства, основанный на разбиении, который может быть более гибким, если вы пытаетесь применить это к вариантам задачи, над которыми математический подход не работает должным образом. Это требует изменения базового массива и имеет худшие постоянные факторы, чем математический подход. Точнее говоря, я считаю, что затраты с точки зрения общего числа значений и количества дубликатов d равны O ( n log d ) и O ( d ) соответственно, хотя для точного подтверждения этого потребуется больше времени, чем у меня на данный момент. ,n d O(nlogd) O(d)
Алгоритм
Начните со списка пар, где первая пара - это диапазон по всему массиву, или если 1 проиндексирован.[(1,n)]
Повторяйте следующие шаги, пока список не станет пустым:
Беглый анализ сложности времени.
Шаги с 1 по 6 занимают время, так как поиск минимума и максимума и разбиение могут быть выполнены за линейное время.O(j−i)
Каждая пара в списке является либо первой парой ( 1 , n ) , либо дочерним элементом некоторой пары, для которой соответствующий подмассив содержит дубликат элемента. Существует не более d ⌈ log 2 n + 1 ⌉ таких родителей, так как каждый обход делит пополам диапазон, в котором может быть дубликат, таким образом, получается не более 2 d ⌈ log 2 n + 1 ⌉ всего при включении пар над подмассивами без дубликаты. Размер списка не более 2 дней(i,j) (1,n) d⌈log2n+1⌉ 2d⌈log2n+1⌉ 2d ,
Рассмотрим работу по поиску любого дубликата. Он состоит из последовательности пар в экспоненциально убывающем диапазоне, поэтому общая работа представляет собой сумму геометрической последовательности или . Это дает очевидное следствие того, что общая работа для d дубликатов должна быть O ( n d ) , которая является линейной по n .O(n) d O(nd) n
Чтобы найти более жесткую границу, рассмотрим наихудший сценарий максимального распространения дубликатов. Интуитивно понятно, что поиск занимает две фазы: одна, где каждый раз просматривается полный массив, в постепенно меньших частях, и одна, где части меньше так что только части массива пройдены. Первая фаза может быть толькоглубинойlogd, поэтому имеет стоимостьO(nlogd), а вторая фаза имеет стоимостьO(n),потому что общая область поиска снова экспоненциально уменьшается.nd logd O(nlogd) O(n)
источник
Оставив это как ответ, потому что ему нужно больше места, чем дает комментарий.
Вы делаете ошибку в ОП, когда предлагаете метод. Сортировка списка с последующим преобразованием его время, а не O ( n 2 log n ) время. Когда вы делаете две вещи (которые принимают O ( f ) и O ( g ) соответственно) последовательно, то результирующая временная сложность составляет O ( f + g ) = O ( max f , g ) (в большинстве случаев).O(nlogn) O(n2logn) O(f) O(g) O(f+g)=O(maxf,g)
Чтобы умножить временные сложности, вам нужно использовать цикл for. Если у вас есть цикл длины и для каждого значения в цикле вы выполняете функцию, которая принимает O ( g ) , тогда вы получите время O ( f g ) .f O(g) O(fg)
Итак, в вашем случае вы сортируете по а затем поперечно по O ( n ), в результате чего O ( n log n + n ) = O ( n log n ) . Если для каждого сравнения алгоритма сортировки вам нужно выполнить вычисление, которое принимает O ( n ) , то это займет O ( n 2 log n ), но здесь это не так.O(nlogn) O(n) O(nlogn+n)=O(nlogn) O(n) O(n2logn)
Если вам интересно мое утверждение о том, что , важно отметить, что это не всегда так. Но если f ∈ O ( g ) или g ∈ O ( f ) (что верно для целого множества общих функций), то оно будет выполнено. Чаще всего это не выполняется, когда включаются дополнительные параметры, и вы получаете выражения типа O ( 2 c n + n log n ) .O(f+g)=O(maxf,g) f∈O(g) g∈O(f) O(2cn+nlogn)
источник
Существует очевидный вариант техники логического массива на месте, использующий порядок элементов в качестве хранилища (где
arr[x] == x
для «найденных» элементов). В отличие от варианта раздела, который может быть оправдан для того, чтобы быть более общим, я не уверен, когда вам на самом деле нужно что-то подобное, но это просто.Это просто многократно помещаетn
arr[idx]
в место,arr[idx]
пока вы не найдете это место уже занято, в этот момент он должен быть дубликатом. Обратите внимание, что общее количество свопов ограничено так как каждый своп делает свое условие выхода корректным.источник
while
цикл работает в среднем за постоянное время. В противном случае, это не алгоритм с линейным временем.Вычтите полученные значения из суммы .∑ni=1i=(n−1)⋅n2
Итак, после времени (при условии, что арифметика равна O (1), чего на самом деле нет, но давайте представим), у вас есть сумма σ 1 из 5 целых чисел от 1 до n:Θ(n) σ1
Предположительно, это не хорошо, верно? Вы не можете понять, как разбить это на 5 различных чисел.
Ах, но это то, где это будет весело! Теперь сделайте то же самое, что и раньше, но вычитать квадраты значений из . Теперь у вас есть:∑ni=1i2
Видишь, куда я иду с этим? Сделайте то же самое для степеней 3, 4 и 5, и вы получите 5 независимых уравнений с 5 переменными. Я уверен, что вы можете решить для .x⃗
источник
Easiest way to solve the problem is to create array in which we will count the apperances for each number in the original array, and then traverse all number from1 to n−5 and check if the number appears more than once, the complexity for this solution in both memory and time is linear, or O(N)
источник
Map an array to
1 << A[i]
and then XOR everything together. Your duplicates will be the numbers where corresponding bit is off.источник
источник
collated[item].append(item)
выполняется за постоянное время. Это действительно так?