Znajdowanie duplikatów w czasie O (n) i przestrzeni O (1)

Dane wejściowe: biorąc pod uwagę tablicę n elementów, która zawiera elementy od 0 do n-1, przy czym każda z tych liczb pojawia się dowolną liczbę razy.

Cel: znaleźć te powtarzające się liczby w O (n) i używając tylko stałej przestrzeni pamięci.

Na przykład niech n wynosi 7, a tablica {1, 2, 3, 1, 3, 0, 6}, odpowiedź powinna wynosić 1 i 3. Sprawdziłem tutaj podobne pytania, ale w odpowiedziach wykorzystano pewne struktury danych, takie jak HashSetitp.

Jakiś skuteczny algorytm do tego samego?

Oto, co wymyśliłem, co nie wymaga dodatkowego bitu znaku:

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

Pierwsza pętla permutuje tablicę, więc jeśli element xwystępuje przynajmniej raz, to jeden z tych wpisów będzie na pozycji A[x].

Zauważ, że może nie wyglądać na O (n) na pierwszy rzut oka, ale tak jest - chociaż ma zagnieżdżoną pętlę, nadal działa w O(N)czasie. Zamiana występuje tylko wtedy, gdy istnieje itaka A[i] != i, a każda zamiana ustawia co najmniej jeden element taki A[i] == i, że wcześniej nie było to prawdą. Oznacza to, że całkowita liczba swapów (a tym samym całkowita liczba wykonań whileciała pętli) wynosi co najwyżej N-1.

Druga pętla wypisuje wartości xfor, które A[x]nie są równe x- ponieważ pierwsza pętla gwarantuje, że jeśli xistnieje co najmniej raz w tablicy, jedno z tych wystąpień będzie w miejscu A[x], oznacza to, że drukuje te wartości, xktórych nie ma w tablica.

(Link Ideone, abyś mógł się nim bawić)

Znakomita odpowiedź caf wypisuje każdą liczbę, która pojawia się k razy w tablicy k-1 razy. To przydatne zachowanie, ale pytanie prawdopodobnie wymaga, aby każdy duplikat był drukowany tylko raz, a on nawiązuje do możliwości zrobienia tego bez przekraczania granic czasu liniowego / stałej przestrzeni. Można to zrobić, zastępując jego drugą pętlę następującym pseudokodem:

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

Wykorzystuje to właściwość, która mpolega na tym, że po uruchomieniu pierwszej pętli, jeśli jakakolwiek wartość pojawi się więcej niż raz, to jeden z tych wyglądów będzie miał właściwą pozycję, a mianowicie A[m]. Jeśli będziemy ostrożni, możemy użyć tej „domowej” lokalizacji do przechowywania informacji o tym, czy jakiekolwiek duplikaty zostały jeszcze wydrukowane, czy nie.

W wersji caf, gdy przeszliśmy przez tablicę, A[i] != isugerowaliśmy, że A[i]jest to duplikat. W mojej wersji opieram się na nieco innym niezmienniku: A[i] != i && A[A[i]] == A[i]oznacza A[i]to, że jest to duplikat , którego wcześniej nie widzieliśmy . (Jeśli pominiesz część „której nie widzieliśmy wcześniej”, resztę można uznać za wynikającą z prawdy niezmiennika kawiarni i gwarancji, że wszystkie duplikaty mają jakąś kopię w lokalizacji domowej). początek (po zakończeniu pierwszej pętli kawiarni) i pokazuję poniżej, że jest utrzymywany po każdym kroku.

Gdy przechodzimy przez tablicę, sukces A[i] != iczęści testu sugeruje, że A[i] może to być duplikat, którego wcześniej nie widziano. Jeśli wcześniej tego nie widzieliśmy, spodziewamy się A[i], że lokalizacja domu wskazuje na siebie - to jest sprawdzane pod kątem drugiej połowy ifwarunku. W takim przypadku drukujemy go i zmieniamy lokalizację początkową, aby wskazywała z powrotem na ten pierwszy znaleziony duplikat, tworząc dwuetapowy „cykl”.

Aby zobaczyć, że ta operacja nie zmienia naszego niezmiennika, załóżmy, że m = A[i]określona pozycja jest isatysfakcjonująca A[i] != i && A[A[i]] == A[i]. To oczywiste, że zmiana robimy ( A[A[i]] = i) będzie działać, aby zapobiec inne wystąpienia non-domu mod bycia wyjście jako duplikaty powodując 2. połowę swoich ifwarunkach zawodzą, ale to będzie działać, gdy iprzybywa do lokalizacji domowej m? Tak, będzie, ponieważ teraz, chociaż iteraz okazuje się, że pierwsza połowa ifwarunku A[i] != ijest prawdziwa, druga połowa sprawdza, czy lokalizacja, na którą wskazuje, jest lokalizacją domową i stwierdza, że ​​tak nie jest. W tej sytuacji już nie wiem czy mczy A[m]był duplikatem wartość, ale wiemy, że tak czy inaczej,zostało to już zgłoszone , ponieważ gwarantuje się, że te 2 cykle nie pojawią się w wyniku pierwszej pętli kawiarni. (Zauważ, że jeśli m != A[m]wtedy dokładnie jeden z mi A[m]występuje więcej niż raz, a drugi nie występuje w ogóle).

Oto pseudokod

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

Przykładowy kod w C ++

Dla stosunkowo małego N możemy użyć operacji div / mod

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

Nie C / C ++, ale w każdym razie

http://ideone.com/GRZPI

Niezbyt ładne, ale przynajmniej łatwo jest zobaczyć właściwości O (N) i O (1). Zasadniczo skanujemy tablicę i dla każdej liczby sprawdzamy, czy odpowiadająca jej pozycja została oznaczona jako już widziana-raz (N), czy już-widziana-wiele razy (N + 1). Jeśli jest oznaczony jako już widziany raz, drukujemy go i wielokrotnie oznaczamy jako już widziany. Jeśli nie jest oflagowany, oznaczamy go już raz widzianym i przenosimy oryginalną wartość odpowiedniego indeksu do bieżącej pozycji (oznaczanie jest operacją destrukcyjną).

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

lub jeszcze lepiej (szybciej, pomimo podwójnej pętli):

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

Jedno rozwiązanie w C to:

#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;
}

Jest to złożoność przestrzeni O (n) i O (1).

Załóżmy, że prezentujemy tę tablicę jako jednokierunkową strukturę danych grafu - każda liczba jest wierzchołkiem, a jej indeks w tablicy wskazuje na inny wierzchołek tworzący krawędź wykresu.

Dla jeszcze większej prostoty mamy indeksy od 0 do n-1 i zakres liczb od 0..n-1. na przykład

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

0 (3) -> 3 (3) to cykl.

Odpowiedź: Wystarczy przejść przez tablicę opartą na indeksach. jeśli a [x] = a [y], to jest to cykl, a zatem duplikat. Przejdź do następnego indeksu i kontynuuj jeszcze raz i tak dalej, aż do końca tablicy. Złożoność: O (n) czas i O (1) przestrzeń.

Mały kod w Pythonie pokazujący metodę caf powyżej:

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] )

Algorytm można łatwo zobaczyć w poniższej funkcji C. Odzyskanie oryginalnej tablicy, chociaż nie jest wymagane, będzie możliwe z każdym wpisem modulo 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 do testowania.

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

Stworzyłem jedną przykładową aplikację na plac zabaw w bardzo krótkim czasie, aby znaleźć duplikaty w czasie 0 (n) złożoności i stałej dodatkowej przestrzeni. Sprawdź adres URL Znajdowanie duplikatów

Rozwiązanie IMP Above działało, gdy tablica zawiera elementy od 0 do n-1, a każda z tych liczb pojawia się dowolną liczbę razy.

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

    }

Jeśli tablica nie jest zbyt duża, to rozwiązanie jest prostsze, tworzy kolejną tablicę o tym samym rozmiarze do zaznaczania.

1 Utwórz bitmapę / tablicę o takim samym rozmiarze jak tablica wejściowa

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

2 zeskanuj swoją tablicę wejściową i zwiększ jej liczbę w powyższej tablicy

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

3 Teraz zeskanuj tablicę check_list i wydrukuj duplikat raz lub tyle razy, ile zostały powielone

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

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

Oczywiście zajmuje to dwa razy więcej miejsca niż rozwiązanie podane powyżej, ale efektywność czasowa wynosi O (2n), czyli w zasadzie O (n).