Java Array, поиск дубликатов
У меня есть массив, и я ищу дубликаты.
duplicates = false;
for(j = 0; j < zipcodeList.length; j++){
for(k = 0; k < zipcodeList.length; k++){
if (zipcodeList[k] == zipcodeList[j]){
duplicates = true;
}
}
}
Однако этот код не работает, когда дубликатов нет. Почему это?
Переведено автоматически
Ответ 1
На носу ответ..
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;
Отредактировано для переключения .equals() обратно на ==, поскольку я где-то читал, что вы используете int, что было неясно в первоначальном вопросе. Также установить k=j+1, чтобы вдвое сократить время выполнения, но оно по-прежнему равно O(n2).
Более быстрый (в пределе) способ
Вот подход, основанный на хэшировании. Вы должны заплатить за автоматическую блокировку, но это O (n) вместо O (n2). Предприимчивый человек мог бы найти примитивный набор хэшей на основе int (мне кажется, в коллекциях Apache или Google есть такая вещь).)
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;
}
Низкий поклон HuyLe
Смотрите Ответ Хьюла для более или менее точного решения, которое, я думаю, требует пары дополнительных шагов:
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;
}
Или просто для компактности
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;
}
Имеет ли это значение?
Ну, итак, я запустил небольшой бенчмарк, который повсюду сомнителен, но вот код:
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");
}
}
}
С помощью 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
С помощью 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
С помощью 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 Побеждает!
Но только на волосок... .ошибка составляет 15 мс для currentTimeMillis(), и в моем бенчмарке есть несколько зияющих дыр. Обратите внимание, что для любого списка длиннее 100000 вы можете просто вернуться true потому что будет дубликат. Фактически, если список является чем-то вроде random , вы можете вернуть true WHP для гораздо более короткого списка. Какова мораль? В конечном итоге, наиболее эффективная реализация:
return true;
И вы не будете ошибаться очень часто.
Ответ 2
Давайте посмотрим, как работает ваш алгоритм:
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.
лучший алгоритм:
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;
Ответ 3
Вы можете использовать bitmap для повышения производительности при работе с большим массивом.
java.util.Arrays.fill(bitmap, false);
for (int item : zipcodeList)
if (!bitmap[item]) bitmap[item] = true;
else break;
ОБНОВЛЕНИЕ: Это мой очень небрежный ответ того времени, я оставил его здесь только для справки. Вам следует обратиться к отличному ответу Андерсоя.
Ответ 4
Для проверки на наличие дубликатов вам нужно сравнить разные пары.