У меня есть массив, и я ищу дубликаты.
duplicates = false;
for(j = 0; j < zipcodeList.length; j++){
for(k = 0; k < zipcodeList.length; k++){
if (zipcodeList[k] == zipcodeList[j]){
duplicates = true;
}
}
}
Однако этот код не работает, когда нет дубликатов. Что это?
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 (n 2).
Здесь используется хэш-подход. Вы должны платить за автобоксинг, но O (n) вместо O (n 2). Предприимчивая душа хотела найти примитивный набор хэшей на основе int (у Apache или Google Collections есть такая вещь, понимает.)
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 для более или менее решения O (n), которое, как мне кажется, нуждается в нескольких дополнительных шагах:
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
Но только за волосы....15ms находится в пределах ошибки для currentTimeMillis(), и в моем тесте есть некоторые зияющие отверстия. Обратите внимание, что для любого списка длиной более 100000 вы можете просто вернуть true, потому что будет дубликат. На самом деле, если список похож на случайный, вы можете вернуть истинный WHP для гораздо более короткого списка. Что такое мораль? В пределе наиболее эффективная реализация:
return true;
И вы не ошибетесь очень часто.
Посмотрите, как работает ваш алгоритм:
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;
Вы можете использовать растровое изображение для лучшей производительности с большим массивом.
java.util.Arrays.fill(bitmap, false);
for (int item : zipcodeList)
if (!bitmap[item]) bitmap[item] = true;
else {
duplicate = true;
break;
}
Чтобы проверить наличие дубликатов, вам нужно сравнить пары отличные.
Потому что вы сравниваете первый элемент массива с самим собой, поэтому он обнаруживает, что существуют дубликаты, даже если они не существуют.
Инициализировать k = j + 1. Вы не будете сравнивать элементы с собой, и вы также не будете дублировать сравнения. Например, j = 0, k = 1 и k = 0, j = 1 сравнивают один и тот же набор элементов. Это позволит удалить сравнение k = 0, j = 1.
Не используйте == использовать .equals.
попробуйте это вместо этого (IIRC, ZipCode необходимо реализовать Comparable, чтобы это работало.
boolean unique;
Set<ZipCode> s = new TreeSet<ZipCode>();
for( ZipCode zc : zipcodelist )
unique||=s.add(zc);
duplicates = !unique;
Как насчет использования этого метода?
HashSet<Integer> zipcodeSet = new HashSet<Integer>(Arrays.asList(zipcodeList));
duplicates = zipcodeSet.size()!=zipcodeList.length;
Вы также можете работать с Set, который не позволяет дублировать в Java.
for (String name : names)
{
if (set.add(name) == false)
{ // your duplicate element }
}
с помощью метода add() и проверки возвращаемого значения. Если add() возвращает false, это означает, что в Set не разрешен элемент, и это ваш дубликат.