Finden von Duplikaten in O (n) Zeit und O (1) Raum

Eingabe: Bei einem Array von n Elementen, das Elemente von 0 bis n-1 enthält, wobei eine dieser Zahlen beliebig oft vorkommt.

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

Zum Beispiel sei n 7 und das Array {1, 2, 3, 1, 3, 0, 6}, die Antwort sollte 1 & 3 sein. Ich habe hier ähnliche Fragen geprüft, aber die Antworten verwendeten einige Datenstrukturen wie HashSetusw.

Irgendein effizienter Algorithmus dafür?

Das habe ich mir ausgedacht, für das kein zusätzliches Vorzeichenbit erforderlich ist:

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, sodass sich xeiner dieser Einträge an der Position befindet , wenn das Element mindestens einmal vorhanden ist A[x].

Beachten Sie, dass es beim ersten Erröten möglicherweise nicht wie O (n) aussieht, aber es ist - obwohl es eine verschachtelte Schleife hat, läuft es immer noch in der O(N)Zeit. Ein Swap findet nur statt, wenn es einen isolchen gibt 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 damit die Gesamtzahl der Ausführungen des whileSchleifenkörpers) höchstens beträgt N-1.

Die zweite Schleife gibt die Werte aus, xfür die A[x]nicht gleich ist. xDa die erste Schleife garantiert, dass xeine dieser Instanzen vorhanden ist , wenn sie mindestens einmal im Array vorhanden ist, A[x]bedeutet dies, dass die Werte gedruckt werden, in xdenen sie nicht vorhanden sind das Array.

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

Die brillante Antwort von caf druckt jede Zahl, die k-mal im Array k-1-mal erscheint. Das ist ein nützliches Verhalten, aber die Frage verlangt wohl, dass jedes Duplikat nur einmal gedruckt wird, und er spielt auf die Möglichkeit an, dies zu tun, ohne die linearen Grenzen von Zeit und konstantem Raum zu überschreiten. Dies kann erreicht werden, indem seine zweite Schleife durch den folgenden Pseudocode ersetzt wird:

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 aus, dass nach dem Ausführen der ersten Schleife, wenn ein Wert mmehr als einmal erscheint, garantiert ist, dass sich eine dieser Erscheinungen an der richtigen Position befindet, nämlich A[m]. Wenn wir vorsichtig sind, können wir diesen "Heimatort" verwenden, um Informationen darüber zu speichern, ob noch Duplikate gedruckt wurden oder nicht.

In der Version von caf wurde beim Durchlaufen des Arrays A[i] != iimpliziert, dass A[i]es sich um ein Duplikat handelt. In meiner Version verlasse ich mich auf eine etwas andere Invariante: Dies A[i] != i && A[A[i]] == A[i]impliziert, dass A[i]es sich um ein Duplikat handelt , das wir zuvor noch nicht gesehen haben . (Wenn Sie den Teil "den wir noch nicht gesehen haben" löschen, kann der Rest durch die Wahrheit der Invariante des Cafés und die Garantie, dass alle Duplikate eine Kopie an einem Heimatort haben, impliziert werden.) Diese Eigenschaft gilt für Der Anfang (nachdem die erste Runde des Cafés beendet ist) und ich zeigen unten, dass er nach jedem Schritt beibehalten wird.

Während wir das Array durchgehen, A[i] != iimpliziert der Erfolg des Tests, dass es A[i] sich um ein Duplikat handeln kann, das zuvor noch nicht gesehen wurde. Wenn wir es noch nicht gesehen haben, erwarten wir, dass A[i]der Heimatort auf sich selbst zeigt - darauf wird in der zweiten Hälfte der ifErkrankung getestet . Wenn dies der Fall ist, drucken wir es aus und ändern den Heimatort, um auf dieses zuerst gefundene Duplikat zu verweisen. Dadurch wird ein zweistufiger "Zyklus" erstellt.

Um zu sehen, dass diese Operation unsere Invariante nicht verändert, nehmen wir an, dass m = A[i]eine bestimmte Position izufriedenstellend ist A[i] != i && A[A[i]] == A[i]. Es ist offensichtlich, dass die von uns vorgenommene Änderung ( A[A[i]] = i) dazu beiträgt, zu verhindern, dass andere Ereignisse außerhalb des Hauses mals Duplikate ausgegeben werden, indem die zweite Hälfte ihrer ifBedingungen fehlschlägt. Funktioniert sie jedoch, wenn sie iam Heimatort eintrifft m? Ja, das wird es, denn jetzt, obwohl iwir bei dieser neuen Version feststellen, dass die erste Hälfte der ifBedingung A[i] != iwahr ist, prüft die zweite Hälfte, ob der Ort, auf den sie zeigt, ein Heimatort ist, und stellt fest, dass dies nicht der Fall ist. In dieser Situation wissen wir nicht mehr, ob der doppelte Wert war moder A[m]war, aber wir wissen das so oder so,Es wurde bereits berichtet , da diese 2 Zyklen garantiert nicht im Ergebnis der ersten Schleife des Cafés erscheinen. (Beachten Sie, dass wenn m != A[m]dann genau eines von mund A[m]mehrmals vorkommt und das andere überhaupt nicht vorkommt.)

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 sind die Eigenschaften O (N) und O (1) leicht zu erkennen. Grundsätzlich scannen wir das Array und sehen für jede Zahl, ob die entsprechende Position bereits einmal gesehen (N) oder mehrfach gesehen (N + 1) markiert wurde. Wenn es bereits einmal gesehen markiert ist, drucken wir es aus und markieren es bereits mehrfach gesehen. Wenn es nicht markiert ist, markieren wir es bereits einmal und verschieben den ursprünglichen Wert des entsprechenden Index an die aktuelle Position (das Markieren ist eine destruktive Operation).

for (i=0; i<a.length; i++) {
  value = a[i];
  if (value >= 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 der Doppelschleife):

for (i=0; i<a.length; i++) {
  value = a[i];
  while (value < N) {
    if (a[value] == N)  {
      a[value] = N+1; 
      print value;
      value = N;
    } else if (a[value] < N) {
      newvalue = value > i ? a[value] : N;
      a[value] = N;
      value = newvalue;
    }
  }
}

Eine Lösung in C ist:

#include <stdio.h>

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.

Nehmen wir an, wir präsentieren dieses Array als unidirektionale Diagrammdatenstruktur - jede Zahl ist ein Scheitelpunkt und sein Index im Array zeigt auf einen anderen Scheitelpunkt, der eine Kante des Diagramms bildet.

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

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

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

Antwort: Durchlaufen Sie einfach das Array anhand von Indizes. Wenn a [x] = a [y] ist, dann ist es ein Zyklus und somit ein Duplikat. Fahren Sie mit dem nächsten Index fort und fahren Sie bis zum Ende eines Arrays fort. Komplexität: O (n) Zeit und O (1) Raum.

Ein winziger Python-Code zur Demonstration der obigen Methode von caf:

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 ist in der folgenden C-Funktion leicht zu erkennen. Abrufen ursprüngliche Arrays, obwohl dies nicht erforderlich ist , möglich sein wird , jede Eingabe modulo unter n .

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();
}

Ich habe schnell eine Beispielspielplatz-App erstellt, um Duplikate in 0 (n) Zeitkomplexität und konstantem zusätzlichen Platz zu finden. Bitte überprüfen Sie die URL Finding Duplicates

Die oben genannte IMP- Lösung funktionierte, wenn ein Array Elemente von 0 bis n-1 enthält, wobei eine dieser Zahlen beliebig oft vorkommt.

private static void printRepeating(int arr[], int size) {
        int i = 0;
        int j = 1;
        while (i < (size - 1)) {
            if (arr[i] == arr[j]) {
                System.out.println(arr[i] + " repeated at index " + j);
                j = size;
            }
            j++;
            if (j >= (size - 1)) {
                i++;
                j = i + 1;
            }
        }

    }

Wenn das Array nicht zu groß ist, ist diese Lösung einfacher. Es wird ein weiteres Array mit derselben Größe zum Aktivieren erstellt.

1 Erstellen Sie eine Bitmap / ein Array mit der gleichen Größe wie Ihr Eingabearray

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

2 Scannen Sie Ihr Eingabearray und erhöhen Sie die Anzahl im obigen Array

for(i=0;i<n;i++) // every element in input array
{
  check_list[a[i]]++; //increment its count  
}  

3 Scannen Sie nun das Array check_list und drucken Sie das Duplikat entweder einmal oder so oft, wie es dupliziert wurde

for(i=0;i<n;i++)
{

    if(check_list[i]>1) // appeared as duplicate
    {
        printf(" ",i);  
    }
}

Natürlich nimmt es doppelt so viel Platz ein wie die oben angegebene Lösung, aber die Zeiteffizienz beträgt O (2n), was im Grunde genommen O (n) ist.