Duplikate in O (n) Zeit und O (1) Raum finden

Eingabe: Gegeben sei ein Array von n Elementen, die Elemente von 0 bis n-1 enthalten, wobei jede dieser Zahlen beliebig oft vorkommen kann.

Ziel: Um diese sich wiederholenden Zahlen in O (n) zu finden und nur konstanten Speicherplatz zu verwenden.

Zum Beispiel sei n 7 und array be {1, 2, 3, 1, 3, 0, 6}, die Antwort sollte 1 und 3 lauten. Ich habe ähnliche Fragen hier geprüft, aber die Antworten verwendeten einige Datenstrukturen wie HashSet usw.

Jeder effiziente Algorithmus für den gleichen?

   

Dies ist, was ich erfunden habe, das das zusätzliche Vorzeichenbit nicht benötigt:

 for i := 0 to n - 1 while A[A[i]] != A[i] swap(A[i], A[A[i]]) end while end for for i := 0 to n - 1 if A[i] != i then print A[i] end if end for 

Die erste Schleife permutiert das Array so, dass, wenn das Element x mindestens einmal vorhanden ist, einer dieser Einträge an der Position A[x] .

Beachten Sie, dass es auf den ersten Blick nicht nach O (n) aussieht, aber es ist – obwohl es eine verschachtelte Schleife hat, läuft es immer noch in O(N) -Zeit. Ein Swap tritt nur auf, wenn es ein i so dass A[i] != i , und jeder Swap setzt mindestens ein Element, so dass A[i] == i , wo das vorher nicht wahr war. Dies bedeutet, dass die Gesamtzahl der Swaps (und somit die Gesamtzahl der Ausführungen des while Schleifenkörpers) höchstens N-1 beträgt.

Die zweite Schleife gibt die Werte von x für die A[x] nicht gleich x – da die erste Schleife garantiert, dass, wenn x mindestens einmal im Array existiert, eine dieser Instanzen bei A[x] , das bedeutet dass es die Werte von x druckt, die nicht in dem Array vorhanden sind.

(Ideone Link, damit Sie damit spielen können)

Cafs brilliante Antwort gibt jede Zahl aus, die k-mal k-mal im Array erscheint. Das ist nützliches Verhalten, aber die Frage erfordert wohl, dass jedes Duplikat nur einmal gedruckt wird, und er spielt auf die Möglichkeit an, dies zu tun, ohne die linearen Zeit- / Konstantraumgrenzen zu durchbrechen. Dies kann durch Ersetzen der zweiten Schleife durch den folgenden Pseudocode erfolgen:

 for (i = 0; i < N; ++i) { if (A[i] != i && A[A[i]] == A[i]) { print A[i]; A[A[i]] = i; } } 

Dies nutzt die Eigenschaft, dass nach der ersten Schleife, wenn irgendein Wert m mehr als einmal auftritt, dann ist eines dieser Erscheinungen garantiert in der richtigen Position, nämlich A[m] . Wenn wir vorsichtig sind, können wir diesen "Heimatort" verwenden, um Informationen darüber zu speichern, ob Duplikate bereits gedruckt wurden oder nicht.

In der caf-Version, als wir durch das Array gingen, implizierte A[i] != i , dass A[i] ein Duplikat ist. In meiner Version verlasse ich mich auf eine etwas andere Invariante: dass A[i] != i && A[A[i]] == A[i] impliziert, dass A[i] ein Duplikat ist , das wir vorher nicht gesehen haben . (Wenn Sie den Teil "dass wir noch nicht gesehen haben" weglassen, kann der Rest durch die Wahrheit der Invariante von Caf und die Garantie, dass alle Duplikate eine Kopie an einem Heimatort haben, gesehen werden.) Diese Eigenschaft gilt für der Anfang (nachdem Cafs erste Schleife beendet ist) und ich zeige unten, dass es nach jedem Schritt beibehalten wird.

Wenn wir durch das Array gehen, impliziert der Erfolg des A[i] != i Teils des Tests, dass A[i] ein Duplikat sein könnte, das vorher nicht gesehen wurde. Wenn wir es vorher noch nicht gesehen haben, dann erwarten wir, dass der Heimatort von A[i] auf sich selbst zeigt - darauf wird in der zweiten Hälfte der if Bedingung getestet. Wenn dies der Fall ist, drucken wir es und ändern den Heimatort, um auf dieses zuerst gefundene Duplikat zu verweisen, wobei ein zweistufiger "Zyklus" erzeugt wird.

Um zu sehen, dass diese Operation unsere Invariante nicht ändert, sei angenommen, dass m = A[i] für eine bestimmte Position i die A[i] != i && A[A[i]] == A[i] erfüllt A[i] != i && A[A[i]] == A[i] . Es ist offensichtlich, dass die von uns vorgenommene Änderung ( A[A[i]] = i ) verhindern wird, dass andere Nicht-Home-Vorkommen von m als Duplikate ausgegeben werden, indem die zweite Hälfte ihrer if Bedingungen fehlschlägt, aber wird es funktionieren wenn i am Heimatort eintreffe, m ? Ja es wird, denn jetzt, obwohl in diesem neuen i wir finden, dass die 1. Hälfte der if Bedingung, A[i] != i , wahr ist, testet die zweite Hälfte, ob der Ort, auf den sie zeigt, ein Heimatort ist und findet, dass es nicht ist. In dieser Situation wissen wir nicht mehr, ob m oder A[m] der doppelte Wert war, aber wir wissen, dass es in beiden Fällen bereits berichtet wurde , weil diese 2 Zyklen garantiert nicht im Ergebnis der 1. Schleife von caf erscheinen. (Beachte, dass, wenn m != A[m] dann genau einer von m und A[m] mehr als einmal vorkommt und der andere überhaupt nicht auftritt.)

Hier ist der Pseudocode

 for i < - 0 to n-1: if (A[abs(A[i])]) >= 0 : (A[abs(A[i])]) = -(A[abs(A[i])]) else print i end for 

Beispielcode in C ++

Für relativ kleine N können wir Div / Mod-Operationen verwenden

 n.times do |i| e = a[i]%n a[e] += n end n.times do |i| count = a[i]/n puts i if count > 1 end 

Nicht C / C ++, aber trotzdem

http://ideone.com/GRZPI

Nicht wirklich hübsch, aber zumindest ist es leicht, die O (N) und O (1) Eigenschaften zu sehen. Im Grunde scannen wir das Array und sehen für jede Nummer, ob die entsprechende Position schon einmal-einmal-gesehen (N) oder schon-mehrfach-gesehen (N + 1) markiert wurde. Wenn es bereits einmal angezeigt wird, drucken wir es und markieren es bereits mehrfach. Wenn es nicht markiert ist, markieren wir es bereits einmal-gesehen und wir verschieben den ursprünglichen Wert des entsprechenden Index an die aktuelle Position (das Markieren ist eine destruktive Operation).

 for (i=0; i= N) continue; if (a[value] == N) { a[value] = N+1; print value; } else if (a[value] < N) { if (value > i) a[i--] = a[value]; a[value] = N; } } 

oder, noch besser (schneller, trotz Doppelschleife):

 for (i=0; i i ? a[value] : N; a[value] = N; value = newvalue; } } } 

Eine Lösung in C ist:

 #include  int finddup(int *arr,int len) { int i; printf("Duplicate Elements ::"); for(i = 0; i < len; i++) { if(arr[abs(arr[i])] > 0) arr[abs(arr[i])] = -arr[abs(arr[i])]; else if(arr[abs(arr[i])] == 0) { arr[abs(arr[i])] = - len ; } else printf("%d ", abs(arr[i])); } } int main() { int arr1[]={0,1,1,2,2,0,2,0,0,5}; finddup(arr1,sizeof(arr1)/sizeof(arr1[0])); return 0; } 

Es ist O (n) Zeit und O (1) Raumkomplexität.

Angenommen, wir präsentieren dieses Array als unidirektionale Graphdatenstruktur – jede Zahl ist ein Eckpunkt und ihr Index im Array zeigt auf einen anderen Eckpunkt, der eine Kante des Graphen bildet.

Für noch mehr Einfachheit haben wir die Indizes 0 bis n-1 und den Zahlenbereich von 0 bis n-1. z.B

  0 1 2 3 4 a[3, 2, 4, 3, 1] 

0 (3) -> 3 (3) ist ein Zyklus.

Antwort: Durchqueren Sie einfach das Array, das auf Indizes basiert. Wenn a [x] = a [y], dann ist es ein Zyklus und somit duplizieren. Springe zum nächsten Index und fahre fort bis zum Ende eines Arrays. Komplexität: O (n) Zeit und O (1) Raum.

Ein kleiner Python-Code, um Cafs Methode oben zu demonstrieren:

 a = [3, 1, 1, 0, 4, 4, 6] n = len(a) for i in range(0,n): if a[ a[i] ] != a[i]: a[a[i]], a[i] = a[i], a[a[i]] for i in range(0,n): if a[i] != i: print( a[i] ) 

Der Algorithmus kann leicht in der folgenden C-function gesehen werden. Das Abrufen des ursprünglichen Arrays, obwohl nicht erforderlich, ist möglich, indem jeder Eintrag modulo n genommen wird .

 void print_repeats(unsigned a[], unsigned n) { unsigned i, _2n = 2*n; for(i = 0; i < n; ++i) if(a[a[i] % n] < _2n) a[a[i] % n] += n; for(i = 0; i < n; ++i) if(a[i] >= _2n) printf("%u ", i); putchar('\n'); } 

Ideone Link zum Testen.

 static void findrepeat() { int[] arr = new int[7] {0,2,1,0,0,4,4}; for (int i = 0; i < arr.Length; i++) { if (i != arr[i]) { if (arr[i] == arr[arr[i]]) { Console.WriteLine(arr[i] + "!!!"); } int t = arr[i]; arr[i] = arr[arr[i]]; arr[t] = t; } } for (int j = 0; j < arr.Length; j++) { Console.Write(arr[j] + " "); } Console.WriteLine(); for (int j = 0; j < arr.Length; j++) { if (j == arr[j]) { arr[j] = 1; } else { arr[arr[j]]++; arr[j] = 0; } } for (int j = 0; j < arr.Length; j++) { Console.Write(arr[j] + " "); } Console.WriteLine(); } 

Wenn das Array nicht zu groß ist, ist diese Lösung einfacher. Es wird ein weiteres Array derselben Größe für das Ticking erstellt.

1 Erstellen Sie eine Bitmap / ein Array derselben Größe wie Ihr Eingabe-Array

  int check_list[SIZE_OF_INPUT]; for(n elements in checklist) check_list[i]=0; //initialize to zero 

2 scannen Sie Ihr Eingabe-Array und erhöhen Sie die Anzahl im obigen Array

 for(i=0;i 

3 Scannen Sie nun das check_list-Array und drucken Sie das Duplikat entweder einmal oder so oft, wie es doppelt vorhanden ist

 for(i=0;i1) // appeared as duplicate { printf(" ",i); } } 

Natürlich benötigt es den doppelten Raum, der von der oben angegebenen Lösung verbraucht wird, aber die Zeiteffizienz ist O (2n), was im Grunde O (n) ist.