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 )
algorithms
arrays
searching
Darylnak
quelle
quelle
Antworten:
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 )B n 0 A B[A[i]] i B A B[A[i]]>1 A[i] O(n) Zeit auf Kosten des Speichers, der und weil Ihre ganzen Zahlen zwischen 1 und n - 5 liegen .O(n) 1 n−5
quelle
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)
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:
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 nd O ( 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)
quelle
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 .n d O(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:
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(j−i)
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) d⌈log2n+1⌉ 2d⌈log2n+1⌉ 2d .
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) d O(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.nd logd O(nlogd) O(n)
quelle
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 ( max f, 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 )f O ( 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 ( n logn ) O ( n ) O ( n logn + n ) = O ( n logn ) 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 ( max f, g) f∈ O ( g) G∈ O ( f) O ( 2cn + n logn )
quelle
Es gibt eine offensichtliche In-Place-Variante der Booleschen Array-Technik, bei der die Reihenfolge der Elemente als Speicher verwendet wird (wo
arr[x] == x
fü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.Diese gerade wiederholt setztn
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.quelle
while
Schleife im Durchschnitt in konstanter Zeit abläuft. Ansonsten ist dies kein linearer Zeitalgorithmus.Subtrahieren Sie Ihre Werte von der Summe .∑ni = 1i = ( n - 1 ) ≤ 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
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:∑ni = 1ich2
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( 5 n6) ⌉
quelle
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 )1 n - 5 O ( N)
quelle
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.quelle
quelle
collated[item].append(item)
in konstanter Zeit ausgeführt wird. Stimmt das wirklich?