Tableau Java, Trouver Des Doublons
J'ai un tableau, et je cherche des doublons.
duplicates = false;
for(j = 0; j < zipcodeList.length; j++){
for(k = 0; k < zipcodeList.length; k++){
if (zipcodeList[k] == zipcodeList[j]){
duplicates = true;
}
}
}
Cependant, ce code ne fonctionne pas quand il n'y a pas de doublons. Pourquoi cela?
13 réponses
Sur la réponse du nez..
duplicates=false;
for (j=0;j<zipcodeList.length;j++)
for (k=j+1;k<zipcodeList.length;k++)
if (k!=j && zipcodeList[k] == zipcodeList[j])
duplicates=true;
Édité pour basculer .equals() vers == depuis que j'ai lu quelque part que vous utilisez int, ce qui n'était pas clair dans la question initiale. Aussi pour définir k=j+1, pour réduire de moitié le temps d'exécution, mais c'est toujours O (n2).
Un moyen plus rapide (dans la limite)
Voici une approche basée sur le hachage. Vous devez payer pour l'autoboxing, mais C'est O (n) au lieu de O (n2). Une âme entreprenante irait trouver un ensemble de hachage primitif basé sur int (Apache ou Google Collections a une telle chose, me semble.)
boolean duplicates(final int[] zipcodelist)
{
Set<Integer> lump = new HashSet<Integer>();
for (int i : zipcodelist)
{
if (lump.contains(i)) return true;
lump.add(i);
}
return false;
}
S'incliner devant HuyLe
Voir la réponse de HuyLe pour une solution plus ou moins O (n), qui, je pense, nécessite quelques étapes supplémentaires:
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;
}
Ou juste pour être Compact
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;
}
Est-ce important?
Eh bien, alors j'ai couru un petit benchmark, qui est incertain partout, Mais voici le code:
import java.util.BitSet;
class Yuk
{
static boolean duplicatesZero(final int[] zipcodelist)
{
boolean duplicates=false;
for (int j=0;j<zipcodelist.length;j++)
for (int k=j+1;k<zipcodelist.length;k++)
if (k!=j && zipcodelist[k] == zipcodelist[j])
duplicates=true;
return duplicates;
}
static boolean duplicatesOne(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] ^= true))
return true;
}
return false;
}
static boolean duplicatesTwo(final int[] zipcodelist)
{
final int MAXZIP = 99999;
BitSet b = new BitSet(MAXZIP + 1);
b.set(0, MAXZIP, false);
for (int item : zipcodelist) {
if (!b.get(item)) {
b.set(item, true);
} else
return true;
}
return false;
}
enum ApproachT { NSQUARED, HASHSET, BITSET};
/**
* @param args
*/
public static void main(String[] args)
{
ApproachT approach = ApproachT.BITSET;
final int REPS = 100;
final int MAXZIP = 99999;
int[] sizes = new int[] { 10, 1000, 10000, 100000, 1000000 };
long[][] times = new long[sizes.length][REPS];
boolean tossme = false;
for (int sizei = 0; sizei < sizes.length; sizei++) {
System.err.println("Trial for zipcodelist size= "+sizes[sizei]);
for (int rep = 0; rep < REPS; rep++) {
int[] zipcodelist = new int[sizes[sizei]];
for (int i = 0; i < zipcodelist.length; i++) {
zipcodelist[i] = (int) (Math.random() * (MAXZIP + 1));
}
long begin = System.currentTimeMillis();
switch (approach) {
case NSQUARED :
tossme ^= (duplicatesZero(zipcodelist));
break;
case HASHSET :
tossme ^= (duplicatesOne(zipcodelist));
break;
case BITSET :
tossme ^= (duplicatesTwo(zipcodelist));
break;
}
long end = System.currentTimeMillis();
times[sizei][rep] = end - begin;
}
long avg = 0;
for (int rep = 0; rep < REPS; rep++) {
avg += times[sizei][rep];
}
System.err.println("Size=" + sizes[sizei] + ", avg time = "
+ avg / (double)REPS + "ms");
}
}
}
Avec 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
Avec 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
Avec 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 gagne!
, Mais seulement par un cheveu... .15ms est dans l'erreur pour currentTimeMillis(), et il y a quelques trous béants dans mon benchmark. Notez que pour toute liste supérieure à 100000, vous pouvez simplement renvoyer true car il y aura un doublon. En fait, si la liste est quelque chose comme aléatoire, vous pouvez retourner TRUE WHP pour une liste beaucoup plus courte. Quelle est la morale? Dans la limite, l'implémentation la plus efficace est:
return true;
Et vous ne vous tromperez pas très souvent.
Voyons comment fonctionne Votre algorithme:
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 meilleur algorithme:
for (j=0;j<zipcodeList.length;j++) {
for (k=j+1;k<zipcodeList.length;k++) {
if (zipcodeList[k]==zipcodeList[j]){ // or use .equals()
return true;
}
}
}
return false;
Vous pouvez utiliser bitmap pour de meilleures performances avec large array.
java.util.Arrays.fill(bitmap, false);
for (int item : zipcodeList)
if (!bitmap[item]) bitmap[item] = true;
else break;
Mise à jour: c'est une réponse très négligente de ma part dans la journée, en la gardant ici juste pour référence. Vous devriez vous référer à l'excellente réponse d'andersoj .
Pour vérifier les doublons, vous devez comparer les pairesdistinctes .
Parce que vous comparez le premier élément du tableau contre lui-même afin Qu'il trouve qu'il y a des doublons même là où il n'y en a pas.
Initialiser k = j + 1. Vous ne comparerez pas les éléments à eux-mêmes et vous ne dupliquerez pas non plus les comparaisons. Par exemple, j = 0, k = 1 et k = 0, j = 1 comparer le même ensemble d'éléments. Cela supprimerait la comparaison k = 0, J = 1.
Ne pas utiliser == utiliser .equals.
Essayez ceci à la place (IIRC, ZipCode doit implémenter Comparable pour que cela fonctionne.
boolean unique;
Set<ZipCode> s = new TreeSet<ZipCode>();
for( ZipCode zc : zipcodelist )
unique||=s.add(zc);
duplicates = !unique;
Vous pouvez également travailler avec Set, qui n'autorise pas les doublons en Java..
for (String name : names)
{
if (set.add(name) == false)
{ // your duplicate element }
}
En utilisant la méthode add () et vérifiez la valeur de retour. Si add () renvoie false, cela signifie que l'élément n'est pas autorisé dans L'ensemble et qu'il s'agit de votre doublon.
public static ArrayList<Integer> duplicate(final int[] zipcodelist) {
HashSet<Integer> hs = new HashSet<>();
ArrayList<Integer> al = new ArrayList<>();
for(int element: zipcodelist) {
if(hs.add(element)==false) {
al.add(element);
}
}
return al;
}
Que diriez-vous d'utiliser cette méthode?
HashSet<Integer> zipcodeSet = new HashSet<Integer>(Arrays.asList(zipcodeList));
duplicates = zipcodeSet.size()!=zipcodeList.length;
@andersoj a donné une excellente réponse, mais je veux aussi ajouter un nouveau moyen simple
private boolean checkDuplicateBySet(Integer[] zipcodeList) {
Set<Integer> zipcodeSet = new HashSet(Arrays.asList(zipcodeList));
if (zipcodeSet.size() == zipcodeList.length) {
return true;
}
return false;
}
Dans le cas où zipcodeList est int [], vous devez d'abord convertir int [] en entier [] (ce n'est pas auto-boxing), code ici
Le code complet sera:
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<Integer> zipcodeSet = new HashSet(Arrays.asList(zipcodeIntegerArray));
if (zipcodeSet.size() == zipcodeList.length) {
return true;
}
return false;
}
Espérons que cela aide!
Affiche tous les éléments dupliqués. Sortie -1 {[3] } lorsqu'aucun élément répétitif n'est trouvé.
import java.util.*;
public class PrintDuplicate {
public static void main(String args[]){
HashMap<Integer,Integer> h = new HashMap<Integer,Integer>();
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; i<arr.length; i++)
arr[i]=s.nextInt();
for(int i=0; i<arr.length; i++){
if(h.containsKey(arr[i])){
h.put(arr[i], h.get(arr[i]) + 1);
arr1[l++]=arr[i];
} else {
h.put(arr[i], 1);
}
}
if(l>0)
{
for(int i=0;i<l;i++)
System.out.println(arr1[i]);
}
else
System.out.println(-1);
}
}
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));
}
}
}
}