Array Java, alla ricerca di duplicati

Ho una matrice e sto cercando i duplicati.

duplicates = false; for(j = 0; j < zipcodeList.length; j++){ for(k = 0; k < zipcodeList.length; k++){ if (zipcodeList[k] == zipcodeList[j]){ duplicates = true; } } } 

Tuttavia, questo codice non funziona quando non ci sono duplicati. Perché?

Alla risposta del naso ..

 duplicates=false; for (j=0;j 

Modificato per cambiare .equals() nuovo su == poiché ho letto da qualche parte che stai usando int , che non era chiaro nella domanda iniziale. Inoltre per impostare k=j+1 , per dimezzare il tempo di esecuzione, ma è ancora O (n 2 ).

Un modo più veloce (nel limite)

Ecco un approccio basato su hash. Devi pagare per l'autoboxing, ma è O (n) invece di O (n 2 ). Un'anima intraprendente troverebbe un set di hash primitivo basato su int (Apache o Google Collections ha una cosa del genere, mi sembra).

 boolean duplicates(final int[] zipcodelist) { Set lump = new HashSet(); for (int i : zipcodelist) { if (lump.contains(i)) return true; lump.add(i); } return false; } 

Saluta su HuyLe

Vedi la risposta di HuyLe per una soluzione più o meno O (n), che credo abbia bisogno di un paio di passaggi aggiuntivi:

 static boolean duplicates(final int[] zipcodelist) { final int MAXZIP = 99999; boolean[] bitmap = new boolean[MAXZIP+1]; java.util.Arrays.fill(bitmap, false); for (int item : zipcodeList) if (!bitmap[item]) bitmap[item] = true; else return true; } return false; } 

O solo per essere compatti

 static boolean duplicates(final int[] zipcodelist) { final int MAXZIP = 99999; boolean[] bitmap = new boolean[MAXZIP+1]; // Java guarantees init to false for (int item : zipcodeList) if (!(bitmap[item] ^= true)) return true; return false; } 

Importa?

Bene, quindi ho eseguito un piccolo punto di riferimento, che è incerto dappertutto, ma ecco il codice:

 import java.util.BitSet; class Yuk { static boolean duplicatesZero(final int[] zipcodelist) { boolean duplicates=false; for (int j=0;j 

Con NSQUARED:

 Trial for size= 10 Size=10, avg time = 0.0ms Trial for size= 1000 Size=1000, avg time = 0.0ms Trial for size= 10000 Size=10000, avg time = 100.0ms Trial for size= 100000 Size=100000, avg time = 9923.3ms 

Con HashSet

 Trial for zipcodelist size= 10 Size=10, avg time = 0.16ms Trial for zipcodelist size= 1000 Size=1000, avg time = 0.15ms Trial for zipcodelist size= 10000 Size=10000, avg time = 0.0ms Trial for zipcodelist size= 100000 Size=100000, avg time = 0.16ms Trial for zipcodelist size= 1000000 Size=1000000, avg time = 0.0ms 

Con BitSet

 Trial for zipcodelist size= 10 Size=10, avg time = 0.0ms Trial for zipcodelist size= 1000 Size=1000, avg time = 0.0ms Trial for zipcodelist size= 10000 Size=10000, avg time = 0.0ms Trial for zipcodelist size= 100000 Size=100000, avg time = 0.0ms Trial for zipcodelist size= 1000000 Size=1000000, avg time = 0.0ms 

BITSET vince!

Ma solo per un capello ... .15ms rientra nell'errore per currentTimeMillis() , e ci sono alcuni buchi nel mio benchmark. Nota che per qualsiasi elenco più lungo di 100000, puoi semplicemente restituire true perché ci sarà un duplicato. Infatti, se la lista è qualcosa di casuale, puoi restituire true WHP per una lista molto più breve. Qual è la morale? Nel limite, l'implementazione più efficiente è:

  return true; 

E non sbaglierai molto spesso.

Vediamo come funziona il tuo algoritmo:

 an array of unique values: [1, 2, 3] check 1 == 1. yes, there is duplicate, assigning duplicate to true. check 1 == 2. no, doing nothing. check 1 == 3. no, doing nothing. check 2 == 1. no, doing nothing. check 2 == 2. yes, there is duplicate, assigning duplicate to true. check 2 == 3. no, doing nothing. check 3 == 1. no, doing nothing. check 3 == 2. no, doing nothing. check 3 == 3. yes, there is duplicate, assigning duplicate to true. 

un algoritmo migliore:

 for (j=0;j 

È ansible utilizzare bitmap per prestazioni migliori con array di grandi dimensioni.

  java.util.Arrays.fill(bitmap, false); for (int item : zipcodeList) if (!bitmap[item]) bitmap[item] = true; else break; 

AGGIORNAMENTO: Questa è una mia risposta molto negligente nel corso della giornata, mantenendola qui solo per riferimento. Dovresti fare riferimento all’eccellente risposta di andersoj.

Per verificare la presenza di duplicati è necessario confrontare coppie distinte .

Perché stai confrontando il primo elemento dell’array contro se stesso in modo che trovi duplicati anche dove non ce ne sono.

Inizializza k = j + 1. Non confronterai gli elementi con se stessi e non duplicherai nemmeno i confronti. Ad esempio, j = 0, k = 1 e k = 0, j = 1 confronta lo stesso insieme di elementi. Ciò rimuoverebbe il confronto k = 0, j = 1.

Non usare == usare .equals .

prova questo (IIRC, ZipCode ha bisogno di implementare Comparable perché funzioni.

 boolean unique; Set s = new TreeSet(); for( ZipCode zc : zipcodelist ) unique||=s.add(zc); duplicates = !unique; 

Puoi anche lavorare con Set, che non consente duplicati in Java ..

  for (String name : names) { if (set.add(name) == false) { // your duplicate element } } 

utilizzando il metodo add () e verificare il valore di ritorno. Se add () restituisce false vuol dire che l’elemento non è consentito nel Set e che è il tuo duplicato.

 public static ArrayList duplicate(final int[] zipcodelist) { HashSet hs = new HashSet<>(); ArrayList al = new ArrayList<>(); for(int element: zipcodelist) { if(hs.add(element)==false) { al.add(element); } } return al; } 

Che ne dici di usare questo metodo?

 HashSet zipcodeSet = new HashSet(Arrays.asList(zipcodeList)); duplicates = zipcodeSet.size()!=zipcodeList.length; 

@andersoj ha dato un’ottima risposta, ma voglio anche aggiungere un nuovo modo semplice

  private boolean checkDuplicateBySet(Integer[] zipcodeList) { Set zipcodeSet = new HashSet(Arrays.asList(zipcodeList)); if (zipcodeSet.size() == zipcodeList.length) { return true; } return false; } 

Nel caso in cui zipcodeList sia int [], è necessario convertire int [] in Integer [] prima (non auto-boxing), codice qui

Il codice completo sarà:

  private boolean checkDuplicateBySet2(int[] zipcodeList) { Integer[] zipcodeIntegerArray = new Integer[zipcodeList.length]; for (int i = 0; i < zipcodeList.length; i++) { zipcodeIntegerArray[i] = Integer.valueOf(zipcodeList[i]); } Set zipcodeSet = new HashSet(Arrays.asList(zipcodeIntegerArray)); if (zipcodeSet.size() == zipcodeList.length) { return true; } return false; } 

Spero che questo ti aiuti!

Stampa tutti gli elementi duplicati. Output -1 quando non vengono trovati elementi ripetuti.

 import java.util.*; public class PrintDuplicate { public static void main(String args[]){ HashMap h = new HashMap(); Scanner s=new Scanner(System.in); int ii=s.nextInt(); int k=s.nextInt(); int[] arr=new int[k]; int[] arr1=new int[k]; int l=0; for(int i=0; i0) { for(int i=0;i 
 import java.util.Scanner; public class Duplicates { public static void main(String[] args) { Scanner console = new Scanner(System.in); int number = console.nextInt(); String numb = "" + number; int leng = numb.length()-1; if (numb.charAt(0) != numb.charAt(1)) { System.out.print(numb.substring(0,1)); } for (int i = 0; i < leng; i++){ if (numb.charAt(i)==numb.charAt(i+1)){ System.out.print(numb.substring(i,i+1)); } else { System.out.print(numb.substring(i+1,i+2)); } } } }