Как найти 5 повторных значений в O (n) времени?

15

Предположим, у вас есть массив размером содержащий целые числа от до включительно, с ровно пятью повторениями. Мне нужно предложить алгоритм, который может найти повторяющиеся числа в времени. Я не могу ни о чем думать. Я думаю, что сортировка, в лучшем случае, будет ? Тогда при обходе массива будет , что приведет к . Тем не менее, я не уверен, что сортировка будет необходима, поскольку я видел некоторые хитрые вещи со связанным списком, очередями, стеками и т. Д.n61n5O(n)O(nlogn)O(n)O(n2logn)

darylnak
источник
16
O(nlogn)+O(n) не является . Это . Было бы если бы вы делали сортировку n раз. O(n2logn)O(nlogn)O(n2logn)
Фонд Моника иск
1
@leftaroundabout Эти алгоритмы: где - размер массива, а - размер входного набора. так как эти алгоритмы работают в O (n ^ 2)n k k = n - c o n s t a n t O ( n 2 )O(kn)nkk=nconstantO(n2)
Roman Gräf
4
@ RomanGräf, похоже, реальная ситуация такова: алгоритмы работают в , где - размер домена. Таким образом, для такой проблемы, как OP, все сводится к тому, используете ли вы такой алгоритм в размерной области или традиционный алгоритм в области неограниченного размера. Имеет смысл тоже. k n O ( n log n )O(logkn)knO(nlogn)
оставил около
5
Для единственным допустимым числом является , согласно вашему описанию. Но тогда придется повторять шесть, а не пять, раз. 1 1n=611
Алекс

Ответы:

22

Вы можете создать дополнительный массив B размером n . Изначально установите все элементы массива на 0 . Затем переберите входной массив A и увеличьте B[A[i]] на 1 для каждого i . После этого вы просто проверяете массив B : цикл над A и если B[A[i]]>1 то A[i] повторяется. Вы решаете это в O(n)время за счет памяти, которая составляет O(n) и потому, что ваши целые числа находятся в диапазоне от 1 до n5 .

fade2black
источник
26

Решение в ответе fade2black является стандартным, но использует пространство O(n) . Вы можете улучшить это до O(1) пространство следующим образом:

  1. Пусть массив будет A[1],,A[n] . Для d=1,,5 вычислим σd=i=1nA[i]d .
  2. Вычислить τd=σdi=1n5id (вы можете использовать известные формулы для вычисления последней суммы в O(1) ). Обратите внимание, что τd=m1d++m5d , где m1,,m5 - повторяющиеся числа.
  3. Вычислить полином P(t)=(tm1)(tm5) . Коэффициенты этого многочлена являются симметричными функциями m1,,m5 которые можно вычислить из τ1,...,τ5 в О(1) .
  4. Найдите все корни многочлена п(T) , испробовав все N-5 возможностей.

Этот алгоритм предполагает модель машины ОЗУ, в которой базовые арифметические операции над -битными словами занимают O ( 1 ) времени.О(журналN)О(1)


Другой способ сформулировать это решение заключается в следующем:

  1. Вычислить , и вывести у 1 = т 1 + + м 5 по формуле у 1 = х 1 - Σ п - 5 я = 1 я .x1=i=1nA[i]y1=m1++m5y1=x1i=1n5i
  2. Вычислите в O ( n ), используя формулу x 2 = ( A [ 1 ] ) A [ 2 ] + ( A [ 1 ] + A [ 2] ] ) A [ 3 ] + ( A [ 1x2=1i<jA[i]A[j]O(n)
    x2=(A[1])A[2]+(A[1]+A[2])A[3]+(A[1]+A[2]+A[3])A[4]++(A[1]++A[n1])A[n].
  3. Выведите , используя формулу у 2 = х 2 - Σ 1 я < J п - 5 я J - ( п - 5 Σ я = 1 я ) у 1 ,y2=1i<j5mimj
    y2=x21i<jn5ij(i=1n5i)y1,
  4. Вычислите и выведите y 3 , y 4 , y 5 по аналогичной линии.x3,Икс4,Икс5Y3,Y4,Y5
  5. Значения являются (с точностью до знака) коэффициентами многочлена P ( t ) из предыдущего решения.Y1,...,Y5п(T)

Это решение показывает, что если мы заменим 5 на , то получим (я полагаю) алгоритм O ( d 2 n ) , используя пространство O ( d 2 ) , которое выполняет O ( d n ) арифметические операции над целыми числами битовой длины O ( d log n ) , сохраняя не более O ( d ) из них в любой момент времени. (Это требует тщательного анализа умножений, которые мы выполняем, большинство из которых включает в себя один операнд длины только O ( log ndО(d2N)О(d2)О(dN)О(dжурналN)О(d) .) Возможно, что это можно улучшить до O ( d n ) времени и O ( d ) пространства с помощью модульной арифметики.О(журналN)О(dN)О(d)

Юваль Фильмус
источник
Любая интерпретация и τ d , P ( t ) , m i и так далее? Почему d { 1 , 2 , 3 , 4 , 5 } ? σdτdп(T)мяd{1,2,3,4,5}
пенополистирол летать
3
В основе решения лежит хитрость суммирования , которая появляется во многих упражнениях (например, как найти отсутствующий элемент из массива длины содержащего все, кроме одного из чисел 1 , , n ?). Трюк суммирования может быть использован для вычисления f ( m 1 ) + + f ( m 5 ) для произвольной функции f , и вопрос в том, какой f выбрать, чтобы иметь возможность вывести m 1 , , mn11,,nf(m1)++f(m5)ff . Мой ответ использует знакомые приемы из элементарной теории симметричных функций. m1,,m5
Юваль
1
@hoffmale На самом деле, . O(d2)
Юваль
1
@hoffmale Каждый из них принимает слова машины. d
Юваль
1
@BurnsBA Проблема этого подхода заключается в том, что намного больше, чем ( n - 4 ) ( n - 5 )(n5)# . Операции с большими числами медленнее. (n4)(n5)2
Юваль
8

Существует также линейный алгоритм времени и постоянного пространства, основанный на разбиении, который может быть более гибким, если вы пытаетесь применить это к вариантам задачи, над которыми математический подход не работает должным образом. Это требует изменения базового массива и имеет худшие постоянные факторы, чем математический подход. Точнее говоря, я считаю, что затраты с точки зрения общего числа значений и количества дубликатов d равны O ( n log d ) и O ( d ) соответственно, хотя для точного подтверждения этого потребуется больше времени, чем у меня на данный момент. ,ndO(nlogd)O(d)


Алгоритм

Начните со списка пар, где первая пара - это диапазон по всему массиву, или если 1 проиндексирован.[(1,n)]

Повторяйте следующие шаги, пока список не станет пустым:

  1. Возьмите и удалите любую пару из списка.(i,j)
  2. Найти минимальное и максимальное, и максимальное обозначенного подмассива.minmax
  3. Если , подмассив состоит только из равных элементов. Получите его элементы, кроме одного, и пропустите шаги с 4 по 6.min=max
  4. Если , подмассив не содержит дубликатов. Пропустите шаги 5 и 6.maxmin=ji
  5. Разбить подмассив вокруг , так что элементы до некоторого индексаkменьше разделителя, а элементы выше этого индекса - нет.min+max2k
  6. Добавьте и ( k + 1 , j ) в список.(i,k)(k+1,j)

Беглый анализ сложности времени.

Шаги с 1 по 6 занимают время, так как поиск минимума и максимума и разбиение могут быть выполнены за линейное время.O(ji)

Каждая пара в списке является либо первой парой ( 1 , n ) , либо дочерним элементом некоторой пары, для которой соответствующий подмассив содержит дубликат элемента. Существует не более d log 2 n + 1 таких родителей, так как каждый обход делит пополам диапазон, в котором может быть дубликат, таким образом, получается не более 2 d log 2 n + 1 всего при включении пар над подмассивами без дубликаты. Размер списка не более 2 дней(i,j)(1,n)dlog2n+12dlog2n+12d,

Рассмотрим работу по поиску любого дубликата. Он состоит из последовательности пар в экспоненциально убывающем диапазоне, поэтому общая работа представляет собой сумму геометрической последовательности или . Это дает очевидное следствие того, что общая работа для d дубликатов должна быть O ( n d ) , которая является линейной по n .O(n)dO(nd)n

Чтобы найти более жесткую границу, рассмотрим наихудший сценарий максимального распространения дубликатов. Интуитивно понятно, что поиск занимает две фазы: одна, где каждый раз просматривается полный массив, в постепенно меньших частях, и одна, где части меньше так что только части массива пройдены. Первая фаза может быть толькоглубинойlogd, поэтому имеет стоимостьO(nlogd), а вторая фаза имеет стоимостьO(n),потому что общая область поиска снова экспоненциально уменьшается.ndlogdO(nlogd)O(n)

Veedrac
источник
Спасибо за объяснение. Теперь я понимаю. Очень красивый алгоритм!
DW
5

Оставив это как ответ, потому что ему нужно больше места, чем дает комментарий.

Вы делаете ошибку в ОП, когда предлагаете метод. Сортировка списка с последующим преобразованием его время, а не 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 ) .fO(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)fO(g)gO(f)O(2cn+nlogn)

Стелла Бидерман
источник
3

Существует очевидный вариант техники логического массива на месте, использующий порядок элементов в качестве хранилища (где arr[x] == xдля «найденных» элементов). В отличие от варианта раздела, который может быть оправдан для того, чтобы быть более общим, я не уверен, когда вам на самом деле нужно что-то подобное, но это просто.

for idx from n-4 to n
    while arr[arr[idx]] != arr[idx]
        swap(arr[arr[idx]], arr[idx])

Это просто многократно помещает arr[idx]в место, arr[idx]пока вы не найдете это место уже занято, в этот момент он должен быть дубликатом. Обратите внимание, что общее количество свопов ограничено так как каждый своп делает свое условие выхода корректным.n

Veedrac
источник
Вам нужно будет привести своего рода аргумент, что внутренний whileцикл работает в среднем за постоянное время. В противном случае, это не алгоритм с линейным временем.
Дэвид Ричерби,
@DavidRicherby В среднем он не работает с постоянным временем, но внешний цикл выполняется только 5 раз, так что это нормально. Обратите внимание, что общее число свопов ограничено так как каждый своп делает правильными свои условия выхода, поэтому даже если количество повторяющихся значений увеличивается, общее время все еще остается линейным (иначе говоря, для этого требуется n шагов, а не n d ). nnnd
Veedrac
К сожалению, я почему-то не заметил, что внешний цикл выполняется постоянное количество раз! (Отредактировано, чтобы включить вашу заметку о количестве свопов, а также, чтобы я мог отменить свое понижение.)
Дэвид Ричерби
1

Вычтите полученные значения из суммы .i=1ni=(n1)n2

Итак, после времени (при условии, что арифметика равна O (1), чего на самом деле нет, но давайте представим), у вас есть сумма σ 1 из 5 целых чисел от 1 до n:Θ(n)σ1

x1+x2+x3+x4+x5=σ1

Предположительно, это не хорошо, верно? Вы не можете понять, как разбить это на 5 различных чисел.

Ах, но это то, где это будет весело! Теперь сделайте то же самое, что и раньше, но вычитать квадраты значений из . Теперь у вас есть:i=1ni2

x12+x22+x32+x42+x52=σ2

Видишь, куда я иду с этим? Сделайте то же самое для степеней 3, 4 и 5, и вы получите 5 независимых уравнений с 5 переменными. Я уверен, что вы можете решить для .x

log(5n6)

einpoklum
источник
Разве @YuvalFilmus не предлагает такое же решение?
fade2black
@ fade2black: О да, это так, извините, я только что увидел первую строчку его решения.
einpoklum
0

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 from 1 to n5 and check if the number appears more than once, the complexity for this solution in both memory and time is linear, or O(N)

someone12321
источник
1
This is the same @fade2black's answer (although a bit easier on the eyes)
LangeHaare
0

Map an array to 1 << A[i] and then XOR everything together. Your duplicates will be the numbers where corresponding bit is off.

Hauleth
источник
There are five duplicates, so the xor trick will not break in some cases.
Evil
1
The running time of this is O(n2). Each bitvector is n bits long, so you each bitvector operation takes O(n) time, and you do one bit vector operation per element of the original array, for a total of O(n2) time.
D.W.
@DW Но, учитывая, что машины, которые мы обычно используем, имеют фиксированные 32 или 64-битные значения, и они не меняются во время выполнения (то есть они постоянны), почему бы их не рассматривать как таковые и предполагать, что битовые операции находятся в О(1) вместо того О(N)?
code_dredd
1
@ray, я думаю, ты ответил на свой вопрос. Учитывая, что машины, которые мы обычно используем, имеют фиксированную скорость 64 бита, время выполнения операции наNвектор О(N)не О(1), Требуется что-то вродеN/64 инструкции сделать некоторые операции на всех N биты N-битный вектор и N/64 является О(N)не О(1),
DW
@DW То, что я получил из пред. комментарии заключались в том, что битовый вектор ссылается на один элемент вNразмерный массив с 64-битным вектором битов, который будет константой, на которую я ссылаюсь. Очевидно, что обработка массива размераN возьму О(КN) время, если мы предположим, что вы К-бит на элемент и Nколичество элементов в массиве. НоКзнак равно64, поэтому операция для элемента массива с постоянным счетом битов должна быть О(1) вместо того О(К) и массив О(N) вместо того О(КN), Вы держитеК ради полноты / правильности или я что-то упускаю?
code_dredd
-2
DATA=[1,2,2,2,2,2]

from collections import defaultdict

collated=defaultdict(list):
for item in DATA:
    collated[item].append(item)
    if len(collated) == 5:
        return item.

# n time
user78484
источник
4
Добро пожаловать на сайт. Мы сайт по информатике , поэтому ищем алгоритмы и объяснения, а не дампы кода, которые требуют понимания конкретного языка и его библиотек. В частности, ваше утверждение о том, что этот код выполняется за линейное время, предполагает, что оно collated[item].append(item)выполняется за постоянное время. Это действительно так?
Дэвид Ричерби
3
Кроме того, вы ищете значение, которое повторяется пять раз. Напротив, OP ищет пять значений, каждое из которых повторяется дважды.
Юваль