trovare il numero duplicato in un array che non ha duplicati ad eccezione di un numero

Question

Supponiamo che ci sia una serie di elementi che non ha duplicati ad eccezione di 1 numero,

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

come trovare il numero di duplicati in modo efficiente maniera? possiamo farlo usando una tabella hash (HT) in tempo O (n) e con O (n) spazio come sotto.

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

C'è un modo migliore in termini di complessità spaziale e temporale?

Nota: questo problema non è un duplicato di sotto due problemi che sono diversi.

Se i numeri interi sono consecutivi la soluzione in questo collegamento può essere utilizzato how-to-find-a-duplicate-element-in-an-array-of-shuffled-consecutive-integers

Se l'array di n elementi contiene elementi da 0 a n-1 solo questo collegamento ha soluzione Finding duplicates in O(n) time and O(1) space

Answer 1

Operazioni su singoli bit richiedono molto tempo (è come: get word, get/set 1 bit, set word), confronta con le operazioni di word (get/set word).

Se si sa che MIN_VALUE> = 0, conosce anche il MAX_VALUE ed è sufficientemente piccolo si può fare qualcosa di simile Jongware suggerito - tabella di hash, ma non su bit: valori hash sono semplicemente che i valori.

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

E inoltre non richiede l'hash di calcolo per ogni elemento.

Answer 2

Non credo che si può fare meglio di O (n) la complessità di tempo - nel peggiore dei casi si sta andando ad avere per toccare ogni elemento del set di dati per trovare il duplicato

Un modo per migliorare il consumo di spazio (al costo di richiedere un po 'di twittling e due passaggi sul set di dati) è quello di utilizzare uno Bloom Filter. L'idea è di fare un primo passaggio sul set di dati: se trovi un possibile duplicato lo rimuovi dal set di dati e lo aggiungi a una tabella hash (se il filtro di fioritura funziona correttamente, solo l'1% circa degli elementi verrà contrassegnato duplicati possibili). Quindi eseguire una seconda passata sul set di dati filtrato, testando gli elementi sulla piccola tabella hash dei possibili duplicati.

Il mio codice sarà in Java poiché è la lingua con cui sono più familiare.

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

Un'alternativa alla tua tabella di hash è quello di utilizzare un Radix Sort, un algoritmo di ordinamento tempo lineare. L'ordinamento Radix avrà prestazioni migliori nel caso peggiore (O (n) per l'ordinamento digitale, rispetto a O (n^2) per la tabella hash nell'improbabile caso in cui si verifichi un numero ridicolo di collisioni), ma prestazioni peggiori nel caso medio (L'implementazione della tabella hash di solito trova il duplicato dopo aver scansionato solo metà del set di dati, mentre l'ordinamento radix richiederà sempre più passaggi sul set di dati). Radix Sort sarà anche marginalmente più efficiente in termini di consumo di spazio se si utilizza una struttura dati efficiente in termini di spazio per i bucket, ad es. una lista chunked.

È possibile parallelizzare l'implementazione della tabella hash senza incorrere in eccessivi sovraccarichi di sincronizzazione. Utilizzando t thread, ogni thread elaborerà n/t elementi del set di dati (ad es.se si dispone di 32 elementi nel set di dati e 2 thread, thread0 elabora gli elementi 0-15 e thread1 elabora gli elementi 16-31), posizionando ciascun elemento in un bucket con indice absoluteValue (x modulo t). Di seguito, ogni thread sarà responsabile dell'elaborazione di tutti gli elementi con un determinato indice bucket, ad es. thread0 elaborerà tutti i bucket con l'indice 0. Sto usando un BlockingQueue per la sincronizzazione - questo consente a un thread di chiamare take() sulla coda, facendo sì che il thread rimuova il primo elemento della coda o blocchi fino a un l'elemento diventa disponibile; tutte le altre strutture dati sono thread-local. Avrai bisogno di inizializzare la variabile dupFinders in modo che un'istanza di DupFinder appaia nello stesso indice di ogni variabile dupFinders di DupFinder (ad es. Thread0 appare sempre nell'indice 0th, assicurando così che tutti gli elementi nel suo BlockingQueue abbiano 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 
    } 
}