Algoritmo per trovare duplicati in un array

Question

Ho un compito per creare un algoritmo per trovare duplicati in un array che include valori numerici. ma non ha detto che tipo di numeri, interi o galleggianti. Ho scritto il seguente pseudocodice:

FindingDuplicateAlgorithm(A) // A is the array 
     mergeSort(A); 
     for int i <- 0 to i<A.length 
      if A[i] == A[i+1] 
       i++ 
       return A[i] 
      else 
       i++ 

ho creato un algoritmo efficiente? Penso che ci sia un problema nel mio algoritmo, restituisce i numeri duplicati più volte. per esempio se array include 2 in due per due indici avrò ... 2, 2, ... nell'output. come posso cambiarlo per restituire ogni duplicato solo una volta? Penso che sia un buon algoritmo per i numeri interi, ma funziona anche per i numeri float?

Answer 1

Per gestire i duplicati, è possibile effettuare le seguenti operazioni:

if A[i] == A[i+1]: 
    result.append(A[i]) # collect found duplicates in a list 
    while A[i] == A[i+1]: # skip the entire range of duplicates 
     i++    # until a new value is found 

Answer 2

Non sono sicuro di quale lingua è necessario scrivere l'algoritmo, ma ci sono alcune ottime soluzioni C++ in risposta a my question qui. Dovrebbe esserti utile.

Answer 3

l'algoritmo contiene un sovraccarico del buffer. i inizia con 0, quindi presumo che gli indici nell'array A siano a base zero, vale a dire il primo elemento è A[0], l'ultimo è A[A.length-1]. Ora i conta fino a A.length-1 e nel corpo del loop accede a A[i+1], che è fuori dall'array per l'ultima iterazione. O, in poche parole: se stai confrontando ogni elemento con l'elemento successivo, puoi fare solo confronti di lunghezza-1.

Se si desidera segnalare solo i duplicati una volta, utilizzare una variabile bool firstDuplicate, impostata su false quando si trova un duplicato e true quando il numero è diverso da quello successivo. Quindi devi solo segnalare il primo duplicato segnalando solo i numeri duplicati se firstDuplicate è vero.

Answer 4

La tua risposta sembra abbastanza buona. Il primo ordinamento e questi semplicemente controllando i valori vicini danno una complessità O(n log(n)) che è abbastanza efficiente.

Unisci tipo è O(n log(n)) mentre il controllo dei valori adiacenti è semplicemente O(n).

Una cosa però (come menzionato in uno dei commenti) si otterrà un overflow dello stack (lol) con lo pseudocodice. Il ciclo interno dovrebbe essere (in Java):

for (int i = 0; i < array.length - 1; i++) { 
    ... 
} 

Poi anche, se si vuole realmente visualizzare i numeri (e o indici) sono i duplicati, è necessario memorizzarli in un elenco separato.

Answer 5

Vuoi trovare duplicati in Java?

È possibile utilizzare un Hashset.

HashSet h = new HashSet(); 
for(Object a:A){ 
    boolean b = h.add(a); 
    boolean duplicate = !b; 
    if(duplicate) 
     // do something with a; 
} 

Il ritorno Valore di add() è definito come:

vero se il set non ha già contengono l'elemento specificato.

EDIT: So HashSet è ottimizzato per inserti e contiene operazioni.Ma non sono sicuro che sia abbastanza veloce per le tue preoccupazioni.

EDIT2: Ti ho visto di recente aggiunto il tag dei compiti. Io non preferisco la mia risposta, se i compiti ITF, perché può essere quello di "alto livello" per un allgorithm-lezione

http://download.oracle.com/javase/1.4.2/docs/api/java/util/HashSet.html#add%28java.lang.Object%29

Answer 6

O (n) algoritmo: traversata l'array e cercare di ingresso ogni elemento un hashtable/set con numero come chiave hash. se non puoi entrare, questo è un duplicato.

Answer 7

public void printDuplicates(int[] inputArray) { 
    if (inputArray == null) { 
     throw new IllegalArgumentException("Input array can not be null"); 
    } 
    int length = inputArray.length; 

    if (length == 1) { 
     System.out.print(inputArray[0] + " "); 
     return; 
    } 

    for (int i = 0; i < length; i++) { 

     if (inputArray[Math.abs(inputArray[i])] >= 0) { 
      inputArray[Math.abs(inputArray[i])] = -inputArray[Math.abs(inputArray[i])]; 
     } else { 
      System.out.print(Math.abs(inputArray[i]) + " "); 
     } 
    } 
}