Wie finde ich 5 wiederholte Werte in O (n) Zeit?

15

Angenommen, Sie haben ein Array der Größe mit ganzen Zahlen von bis einschließlich , wobei genau fünf wiederholt werden. Ich muss einen Algorithmus vorschlagen, der die wiederholten Zahlen in Zeit findet. Ich kann für mein Leben an nichts denken. Ich denke, das Sortieren wäre bestenfalls ? Dann wäre das Durchlaufen des Arrays , was zu . Ich bin mir jedoch nicht sicher, ob eine Sortierung notwendig wäre, da ich einige knifflige Dinge mit verknüpften Listen, Warteschlangen, Stapeln usw. gesehen habe.1 n - 5 O ( n ) O ( n log n ) O ( n ) O ( n 2 log n )n61n5O(n)O(nlogn)O(n)O(n2logn)

Darylnak
quelle
16
O ( n 2 log n ) O ( n log n ) O ( n 2 log n )O(nlogn)+O(n) ist nicht . Es ist . Es wäre wenn Sie die Sortierung n-mal durchführen würden. O(n2logn)O(nlogn)O(n2logn)
Fund Monica's Lawsuit
1
@leftaroundabout Diese Algorithmen sind wobei die Größe des Arrays und die Größe der Eingabemenge ist. da funktionieren diese Algorithmen inn 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 es die aktuelle Situation erscheint , ist dies: die Algorithmen in Arbeit O(logkn) , wobei k die Größe der Domäne ist. Für ein Problem wie das der OPs kommt es also darauf an, ob Sie einen solchen Algorithmus in der Domäne mit n Größen oder einen herkömmlichen O(nlogn) -Algorithmus in einer Domäne mit unbegrenzter Größe verwenden. Macht auch Sinn.
linksum den
5
Für n=6 , ist die einzige zulässige Zahl 1 , indem Sie Ihre Beschreibung. Aber dann 1 müßten sechs wiederholt werden, nicht fünf, mal.
Alex Reinking

Antworten:

22

Sie können ein zusätzliches Array der Größe n erstellen . Setzen Sie zunächst alle Elemente des Arrays auf 0 . Durchlaufen Sie dann das Eingangsarray A und erhöhen Sie B [ A [ i ] ] für jedes i um 1 . Danach überprüfen Sie einfach das Array B : Schleife über A und wenn B [ A [ i ] ] > 1, dann wird A [ i ] wiederholt. Sie lösen es in O ( n )Bn0AB[A[i]]iBAB[A[i]]>1A[i]O(n)Zeit auf Kosten des Speichers, der und weil Ihre ganzen Zahlen zwischen 1 und n - 5 liegen .O(n)1n5

fade2black
quelle
26

Die Lösung in der Antwort von fade2black ist die Standardlösung, sie verwendet jedoch -Raum. Sie können dies wie folgt auf O ( 1 ) verbessern :O(n)O(1)

  1. Sei das Array . Berechnen Sie für d = 1 , , 5 σ d = n i = 1 A [ i ] d .A[1],,A[n]d=1,,5σd=i=1nA[i]d
  2. Berechnen Sie (Sie können die bekannte Formel verwenden, um die letztere Summe in O ( 1 ) zu berechnen ). Man beachte, dass τ d = m d 1 + + m d 5 ist , wobei m 1 , ... , m 5 die wiederholten Zahlen sind.τd=σdi=1n5idO(1)τd=m1d++m5dm1,,m5
  3. Berechnen Sie das Polynom . Die Koeffizienten dieses Polynoms sind symmetrische Funktionen von m 1 , , m 5 , die aus τ 1 , , τ 5 in O ( 1 ) berechnet werden können .P(t)=(tm1)(tm5)m1,,m5τ1,,τ5O(1)
  4. Finden Sie alle Wurzeln des Polynoms indem Sie alle n - 5 Möglichkeiten ausprobieren .P(t)n5

Dieser Algorithmus nimmt das RAM-Maschinenmodell an, bei dem grundlegende arithmetische Operationen an -Bit-Wörtern O ( 1 ) Zeit benötigen .O(logn)O(1)


Eine andere Möglichkeit, diese Lösung zu formulieren, ist die folgende:

  1. Berechnen Sie und leiten Sie y 1 = m 1 + + m 5 nach der Formel y 1 = x 1 - n - 5 i = 1 i .x1=i=1nA[i]y1=m1++m5y1=x1i=1n5i
  2. Berechnen Sie in O ( n ) mit der Formel 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. Deduziere unter Verwendung der Formel y 2 = x 2 - Σ 1 i < j n - 5 i j - ( n - 5 Σ i = 1 i ) y 1 .y2=1i<j5mimj
    y2=x21i<jn5ij(i=1n5i)y1.
  4. Berechnen Sie und leiten Sie y 3 , y 4 , y 5 entlang ähnlicher Linien ab.x3,x4,x5y3,y4,y5
  5. Die Werte von sind (bis zum Vorzeichen) die Koeffizienten des Polynoms P ( t ) aus der vorhergehenden Lösung.y1,,y5P(t)

Diese Lösung zeigt, dass, wenn wir 5 durch ersetzen , wir (glaube ich) einen O ( d 2 n ) -Algorithmus erhalten, der O ( d 2 ) -Raum verwendet und O ( d n ) -Arithmetikoperationen mit ganzen Zahlen der Bitlänge O ausführt ( d log n ) , wobei zu jedem Zeitpunkt höchstens O ( d ) von diesen beibehalten werden. (Dies erfordert eine sorgfältige Analyse der von uns durchgeführten Multiplikationen, von denen die meisten nur einen Operanden der Länge O ( log ndO(d2n)O(d2)O(dn)O(dlogn)O(d) .) Es ist denkbar, dass diesdurch modulare Arithmetikauf O ( d n ) Zeit und O ( d ) Raumverbessertwerden kann.O(logn)O(dn)O(d)

Yuval Filmus
quelle
Jede Interpretation von und τ d , P ( t ) , m i und so weiter? Warum ist d { 1 , 2 , 3 , 4 , 5 } ? σdτdP(t)mid{1,2,3,4,5}
Styropor fliegen
3
Die Einsicht hinter der Lösung ist der Summationstrick , der in vielen Übungen vorkommt (wie finden Sie beispielsweise das fehlende Element aus einem Array der Länge das alle bis auf eine der Zahlen 1 , , n enthält ?). Der Summationstrick kann verwendet werden, um f ( m 1 ) + + f ( m 5 ) für eine beliebige Funktion f zu berechnen , und die Frage ist, welches f zu wählen ist, um m 1 , , m ableiten zu könnenn11,,nf(m1)++f(m5)ff . Meine Antwort verwendet bekannte Tricks aus der Elementartheorie der symmetrischen Funktionen. m1,,m5
Yuval Filmus
1
@hoffmale Eigentlich . O(d2)
Yuval Filmus
1
@hoffmale Jeder von ihnen nimmt Maschinenwörter. d
Yuval Filmus
1
@BurnsBA Das Problem bei diesem Ansatz ist, dass viel größer ist als ( n - 4 ) ( n - 5 )(n5)# . Operationen mit großen Zahlen sind langsamer. (n4)(n5)2
Yuval Filmus
8

Es gibt auch einen linearen Algorithmus für Zeit und konstanten Raum, der auf Partitionierung basiert. Dieser Algorithmus ist möglicherweise flexibler, wenn Sie versuchen, dies auf Varianten des Problems anzuwenden, bei denen der mathematische Ansatz nicht gut funktioniert. Dies erfordert eine Mutation des zugrunde liegenden Arrays und hat schlechtere konstante Faktoren als der mathematische Ansatz. Genauer gesagt, glaube ich , in Bezug auf die Gesamtzahl der Werte der Kosten und die Anzahl der Duplikate d sind O ( n log d ) und O ( d ) jeweils mehr Zeit rigoros obwohl Beweis nehmen , als ich im Moment haben .ndO(nlogd)O(d)


Algorithmus

Beginnen Sie mit einer Liste von Paaren, wobei das erste Paar der Bereich über das gesamte Array ist oder wenn 1-indiziert.[(1,n)]

Wiederholen Sie die folgenden Schritte, bis die Liste leer ist:

  1. Nimm ein beliebiges Paar aus der Liste und entferne es .(i,j)
  2. Finden Sie die minimale und maximale, und max , des bezeichneten Subarray.minmax
  3. Wenn , besteht das Subarray nur aus gleichen Elementen. Gib seine Elemente mit einer Ausnahme aus und überspringe die Schritte 4 bis 6.min=max
  4. Wenn , enthält das Subarray keine Duplikate. Überspringen Sie die Schritte 5 und 6.maxmin=ji
  5. Partitionieren Sie das Subarray um , so dass Elemente bis zu einem gewissen Indexkkleiner als das Trennzeichen sind und Elemente über diesem Index nicht.min+max2k
  6. Fügen Sie der Liste und ( k + 1 , j ) hinzu .(i,k)(k+1,j)

Kursive Analyse der Zeitkomplexität.

Die Schritte 1 bis 6 benötigen die Zeit , da das Finden des Minimums und Maximums und das Partitionieren in linearer Zeit erfolgen können.O(ji)

Jedes Paar in der Liste ist entweder das erste Paar ( 1 , n ) oder ein Kind eines Paares, für das das entsprechende Subarray ein doppeltes Element enthält. Es gibt höchstens d log 2 n + 1 solche Eltern Da jeder Traversierung Hälften in dem der Bereich ein Duplikat sein kann, so gibt es höchstens 2 d log 2 n + 1 Gesamt wenn einschließlich Paaren über Subarrays mit nein Duplikate. Zu jedem Zeitpunkt beträgt die Größe der Liste nicht mehr als 2 Tage(i,j)(1,n)dlog2n+12dlog2n+12d.

Betrachten Sie die Arbeit, um ein Duplikat zu finden. Dies besteht aus einer Folge von Paaren über einen exponentiell abnehmenden Bereich, so dass die Gesamtarbeit die Summe der geometrischen Folge oder . Dies ergibt eine offensichtliche Folgerung, dass die Gesamtarbeit für d Duplikate O ( n d ) sein muss , was in n linear ist .O(n)dO(nd)n

Um eine engere Grenze zu finden, betrachten Sie das Worst-Case-Szenario, bei dem Duplikate maximal verteilt werden. Intuitiv dauert die Suche zwei Phasen, eine, bei der jedes Mal das gesamte Array durchlaufen wird, und eine, bei der die Teile kleiner als so werden nur Teile des Arrays durchlaufen. Die erste Phase kann nurlogdtief sein, hat also die KostenO(nlogd), und die zweite Phase hat die KostenO(n),weil die gesuchte Gesamtfläche wieder exponentiell abnimmt.ndlogdO(nlogd)O(n)

Veedrac
quelle
Vielen Dank für die Erklärung. Jetzt verstehe ich. Ein sehr hübscher Algorithmus!
DW
5

Lassen Sie dies als Antwort, weil es mehr Platz braucht, als ein Kommentar gibt.

Sie machen im OP einen Fehler, wenn Sie eine Methode vorschlagen. Sortieren einer Liste und anschließendes Übertragen Zeit, nicht O ( n 2 log n ) Zeit. Wenn Sie zwei Dinge hintereinander ausführen ( O ( f ) bzw. O ( g ) ), dann ist die resultierende Zeitkomplexität O ( f + g ) = O ( max f , g ) (unter den meisten Umständen).O(nlogn)O(n2logn)O(f)O(g)O(f+g)=O(maxf,g)

Um die Zeitkomplexität zu multiplizieren, müssen Sie eine for-Schleife verwenden. Wenn Sie eine Schleife der Länge und für jeden Wert in der Schleife eine Funktion ausführen, die , erhalten Sie Zeit.O ( g ) O ( f g )fO(g)O(fg)

In Ihrem Fall sortieren Sie also in und dann quer in was zu . Wenn Sie für jeden Vergleich des Sortieralgorithmus eine Berechnung durchführen müssten , die , dann würde sie benötigen, aber das ist hier nicht der Fall.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)


Falls Sie neugierig auf meine Behauptung sind, dass , ist es wichtig zu beachten, dass dies nicht immer zutrifft. Wenn jedoch oder (was für eine ganze Reihe gemeinsamer Funktionen gilt) gilt, gilt dies. Die häufigste Zeit, die es nicht dauert, ist, wenn zusätzliche Parameter einbezogen werden und Ausdrücke wie .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)

Stella Biderman
quelle
3

Es gibt eine offensichtliche In-Place-Variante der Booleschen Array-Technik, bei der die Reihenfolge der Elemente als Speicher verwendet wird (wo arr[x] == xfür "gefundene" Elemente). Im Gegensatz zu der Partitionsvariante , die allgemeiner sein kann, bin ich mir nicht sicher, wann Sie tatsächlich so etwas benötigen, aber es ist einfach.

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

Diese gerade wiederholt setzt arr[idx]an der Stelle , arr[idx]bis Sie feststellen , dass Standort bereits genommen, an welcher Stelle es muss ein Duplikat sein. Beachten Sie, dass die Gesamtzahl der Auslagerungen durch begrenzt ist, da bei jeder Auslagerung die Austrittsbedingung korrekt ist.n

Veedrac
quelle
Sie müssen eine Art Argument angeben, dass die innere whileSchleife im Durchschnitt in konstanter Zeit abläuft. Ansonsten ist dies kein linearer Zeitalgorithmus.
David Richerby
@DavidRicherby Es wird im Durchschnitt keine konstante Zeit ausgeführt, aber die äußere Schleife wird nur fünfmal ausgeführt, das ist in Ordnung. Beachten Sie, dass die Gesamtzahl der Swaps begrenzt ist durch , da jeder Swap - Zustand korrekt seinen Ausgang macht, so dass selbst wenn die Anzahl der doppelten Werte die Gesamtzeit erhöht , ist noch linear (aka. Es dauert n Schritte statt n d ). nnnd
Veedrac
Hoppla, irgendwie habe ich nicht bemerkt, dass die äußere Schleife konstant oft läuft! (Bearbeitet, um Ihre Notiz über die Anzahl der Swaps aufzunehmen und auch, damit ich meine Ablehnung umkehren kann.)
David Richerby
1

Subtrahieren Sie Ihre Werte von der Summe .i=1ni=(n1)n2

Also, nach Zeit (unter der Annahme, dass die Arithmetik O (1) ist, was nicht wirklich der Fall ist, aber geben wir vor), haben Sie eine Summe σ 1 von 5 ganzen Zahlen zwischen 1 und n:Θ(n)σ1

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

Angeblich ist das nicht gut, oder? Man kann unmöglich herausfinden, wie man dies in 5 verschiedene Zahlen aufteilt.

Ah, aber hier wird es Spaß! Nun mache dasselbe wie zuvor, aber subtrahiere die Quadrate der Werte von . Jetzt hast du:i=1ni2

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

Sehen Sie, wohin ich damit gehe? Machen Sie dasselbe für Potenzen 3, 4 und 5 und Sie haben 5 unabhängige Gleichungen in 5 Variablen. Ich bin mir ziemlich sicher, dass Sie lösen können .x

Vorsichtsmaßnahmen: Arithmetik ist nicht wirklich O (1). Außerdem benötigen Sie etwas Platz, um Ihre Summen darzustellen. aber nicht so viel, wie Sie sich vorstellen - Sie können fast alles modular machen, solange Sie, oh, Bits haben; das sollte es tun.log(5n6)

einpoklum
quelle
Schlägt @YuvalFilmus nicht dieselbe Lösung vor?
fade2black
@ fade2black: Oh ja, tut es, sorry, ich habe gerade die erste Zeile seiner Lösung gesehen.
Einpoklum
0

Der einfachste Weg, das Problem zu lösen, besteht darin, ein Array zu erstellen, in dem wir die Erscheinungen für jede Zahl im ursprünglichen Array zählen, dann alle Zahlen von bis n - 5 durchlaufen und prüfen, ob die Zahl mehr als einmal vorkommt Lösung sowohl im Gedächtnis als auch in der Zeit ist linear, oder O ( N )1n5O(N)

jemand12321
quelle
1
Dies ist die gleiche Antwort von @ fade2black (obwohl es ein bisschen
augenschonender ist
0

Ordnen Sie ein Array zu 1 << A[i]und XORen Sie dann alles zusammen. Ihre Duplikate sind die Zahlen, bei denen das entsprechende Bit deaktiviert ist.

Holeth
quelle
Es gibt fünf Duplikate, sodass der xor-Trick in einigen Fällen nicht funktioniert.
Evil
1
O(n2)nO(n)O(n2)
O(1)O(n)
1
nO(n)O(1)n/64nnn/64O(n)O(1)
nnO(kn)knk=64O(1)O(k)O(n)O(kn)k
-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
quelle
4
Willkommen auf der Seite. Wir sind eine Informatik - Site, also suchen wir nach Algorithmen und Erklärungen, nicht nach Codedumps, die Kenntnisse einer bestimmten Sprache und ihrer Bibliotheken erfordern. Insbesondere wird bei Ihrer Behauptung, dass dieser Code in linearer Zeit ausgeführt wird, davon ausgegangen, dass er collated[item].append(item)in konstanter Zeit ausgeführt wird. Stimmt das wirklich?
David Richerby
3
Außerdem suchen Sie nach einem Wert, der fünfmal wiederholt wird. Im Gegensatz dazu sucht das OP nach fünf Werten, die sich jeweils zweimal wiederholen.
Yuval Filmus