odnaleźć duplikaty liczby w tablicy, która nie ma duplikatów wyjątkiem jednego numeru

Question

Załóżmy, że istnieje szereg elementów, które nie ma duplikatów wyjątkiem 1 numeru,

ex. 1,2,13,4,7,11,2,6 

Jak znaleźć duplikat numeru w sposób skuteczny sposób? możemy to zrobić za pomocą tabeli mieszania (HT) w czasie O (n) i O (n), jak poniżej.

if(HT.Contains(item)) -> this is the duplicate 
else 
ht.add(item) 

Czy istnieje lepszy sposób pod względem złożoności przestrzeni i czasu?

Uwaga: ten problem nie jest duplikatem poniższych dwóch problemów:, które są różne.

Jeżeli całkowite są z kolei rozwiązanie, w tym związku można stosować how-to-find-a-duplicate-element-in-an-array-of-shuffled-consecutive-integers

Jeśli tablica n elementów zawiera elementy od 0 do n-1, tylko Związek ten roztworowi Finding duplicates in O(n) time and O(1) space

Answer 1

operacji na pojedynczych bitach są czasochłonne (to jak: pobierz słowo, get/ustaw 1 bit, ustaw słowo), porównaj z operacjami na słowach (get/set word).

Jeśli wiesz, że MIN_VALUE> = 0, znasz również wartość MAX_VALUE i jest ona wystarczająco mała, możesz zrobić coś takiego, jak sugerował Jongware - tablica haszująca, ale nie na bitach: wartości zakodowane są po prostu wartościami.

#include <stdio.h> 
#include <string.h> 

#define MAX_VALUE 13 +1 // +1 so we don't have do -1 in for loop 

main() 
{ 
    int i; 
    int array[] = { 1,2,13,4,7,11,2,6 }; 
    int array_size = sizeof(array)/sizeof(array[0]); 

    short flags[MAX_VALUE] = { 0 }; 
    for (i = 0; i < array_size; ++i) { 
      if (++flags[ array[i] ] != 1) { 
       printf ("duplicated %d on %d\th position", array[i], i); 
      } 
    } 
} 

Nie wymaga to również mieszania obliczeniowego dla każdego elementu.

Answer 2

Nie sądzę, można to zrobić lepiej niż O (N) złożoności czasowej - w najgorszym wypadku będziesz musiał dotknąć każdy element zbioru danych, aby znaleźć duplikaty

Jednym ze sposobów poprawy Zużycie przestrzeni (kosztem wymagającego odrobiny twiddlingu, a także dwóch przebiegów przez zbiór danych) jest użycie Bloom Filter. Pomysł polega na pierwszym przejściu przez zbiór danych: jeśli znajdziesz możliwy duplikat, usuń go z zestawu danych i dodaj go do tablicy mieszającej (jeśli filtr kwitnący działa poprawnie, to tylko około 1% elementów zostanie oznaczonych flagą w miarę możliwości duplikaty). Następnie przeprowadź drugie przejście przez przefiltrowany zbiór danych, testując elementy pod kątem małej tablicy mieszania możliwych duplikatów.

Mój kod będzie w Javie, ponieważ jest to język, który jestem najbardziej znany.

Class DupFinder { 
    BloomFilter filter = new BloomFilter(); 
    HashTable hashTable = new HashTable(); 
    int start = 0; 

    int run(int[] dataset) { 
    // first pass 
    for(int i = 0; i < dataset.length; i++) { 
     if(filter.contains(dataset[i]) { 
     // check if element is in hashTable, else add it 
     if(hashTable.contains(dataset[i]) { 
      return dataset[i]; // duplicate found 
     } else { 
      hashTable.add(dataset[i]); 
     } 

     // remove element from dataset 
     int temp = dataset[start]; 
     dataset[start] = dataset[i]; 
     dataset[i] = temp; 
     start++; 
     } else filter.add(dataset[i]); 
    } 

    // second pass 
    for(int i = start; i < dataset.length; i++) { 
     if(hashTable.contains(dataset[i]) { 
     return dataset[i]; // duplicate found 
     } 
    } 
    return NULL; // no duplicate found 
    } 
} 

Alternatywą do tabeli hash jest użycie Radix Sort, algorytm sortowania czasie liniowym. Sortowanie Radix będzie miało lepszą wydajność w najgorszym przypadku (O (n) dla sortowania radix, w porównaniu do O (n^2) dla tabeli mieszania w mało prawdopodobnym przypadku, gdy napotkasz śmieszną liczbę kolizji), ale gorsza wydajność średniej wielkości (Implementacja tablicy hash będzie zwykle znajdować duplikat po zeskanowaniu tylko połowy zestawu danych, podczas gdy sortowanie radix zawsze będzie wymagało wielu przejść przez zbiór danych). Sortowanie Radix będzie również nieznacznie bardziej wydajne pod względem wykorzystania przestrzeni, jeśli użyjesz przestrzennej struktury danych dla wiader, np. lista porcji.

Można dokonać równoległej implementacji tabeli mieszania bez ponoszenia nadmiernych kosztów synchronizacji. Używając wątków t, każdy wątek przetwarza elementy zbioru danych (np.jeśli masz 32 elementy w zestawie danych i 2 wątki, wątek0 przetwarza elementy 0-15, a wątek1 przetwarza elementy 16-31), umieszczając każdy element w wiadrze z indeksem absoluteValue (x modulo t). Następnie każdy wątek będzie odpowiedzialny za przetwarzanie wszystkich elementów z danym indeksem wiadra, np. thread0 przetworzy wszystkie segmenty z indeksem 0. Do synchronizacji używam BlockingQueue - umożliwia to wątkowi wywołanie take() w kolejce, powodując, że wątek usuwa pierwszy element kolejki lub blokuje do momentu element staje się dostępny; wszystkie inne struktury danych są wątkowo lokalne. Będziesz musiał zainicjować zmienną dupFinders, aby wystąpienie DupFinder pojawiło się w tym samym indeksie każdej zmiennej DupFindera dupFinders (np. Thread0 zawsze pojawia się w indeksie 0, zapewniając w ten sposób, że wszystkie elementy w jego klasie BlockingQue mają absoluteValue (x modulo t) == 0).

Class DupFinder implements Callable<Integer> { 
    private Class Chunk { 
    int size = 0; 
    int chunk = new int[64]; 

    boolean add(int x) { 
     if(size < 64) { 
     chunk[size] = x; 
     size++; 
     return true; 
     } else return false; 
    } 
    } 

    int t = ??? // number of threads 
    private BlockingQueue<Stack<Chunk>> queue = new LinkedBlockingQueue() 
    private DupFinder[] dupFinders = new DupFinder[t]; 
    private Stack<Chunk>[] stacks = new Stack<Chunk>[t]; 

    void add(Stack<Chunk> stack) { 
    queue.add(stack); 
    } 

    // the thread only receives n/t elements of the dataset 
    int call(int[] partialDataset) { 
    // partition dataset elements by their modulus(t) 
    for(int i = 0; i < partialDataset.length; i++) { 
     tempStack = stacks[Math.absoluteValue(partialDataset[i] modulo t)]; 
     if(!tempStack.peek().add(partialDataset[i])) { 
     Chunk chunk = new Chunk(); 
     chunk.add(partialDataset[i]); 
     tempStack.push(chunk); 
     } 
    } 

    // distribute chunk stacks to the appropriate threads 
    for(int i = 0; i < t; i++) { 
     dupFinders[i].add(stacks[i]); 
    } 

    HashTable hashTable = new HashTable(); 
    for(int i = 0; i < t; i++) { 
     // wait for a chunk stack to become available 
     Stack<Chunk> tempStack = queue.take(); 
     while(!tempStack.isEmpty) { 
     tempChunk = tempStack.pop(); 
     for(int i = 0; i < tempChunk.size; i++) { 
      if(hashTable.contains(tempChunk.chunk[i]) { 
      return tempChunk.chunk[i]; // duplicate found 
      } else { 
      hashTable.add(tempChunk.chunk[i]); 
      } 
     } 
     } 
    } 
    return NULL; // no duplicate found 
    } 
}