Java 数组，查找重复项 [英] Java Array, Finding Duplicates
问题描述
我有一个数组，正在寻找重复项.
I have an array, and am looking for duplicates.
duplicates = false;
for(j = 0; j < zipcodeList.length; j++){
for(k = 0; k < zipcodeList.length; k++){
if (zipcodeList[k] == zipcodeList[j]){
duplicates = true;
}
}
}
但是，此代码在没有重复项时不起作用.为什么?
However, this code doesnt work when there are no duplicates. Whys that?
推荐答案
在鼻子上回答..
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).
Edited to switch .equals() back to == since I read somewhere you're using int, which wasn't clear in the initial question. Also to set k=j+1, to halve execution time, but it's still O(n2).
这是一种基于哈希的方法.您必须为自动装箱付费，但它是 O(n) 而不是 O(n2).一个有进取心的人会去寻找一个原始的基于 int 的哈希集(我认为 Apache 或 Google Collections 有这样的东西.)
Here's a hash based approach. You gotta pay for the autoboxing, but it's O(n) instead of O(n2). An enterprising soul would go find a primitive int-based hash set (Apache or Google Collections has such a thing, methinks.)
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 鞠躬
请参阅HuyLe 的答案，了解或多或少的 O(n) 解决方案，我认为这需要几个附加步骤:
Bow to HuyLe
See HuyLe's answer for a more or less O(n) solution, which I think needs a couple of add'l steps:
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;
}
重要吗?
好吧，所以我运行了一个小基准测试，到处都是不确定的，但代码如下:
Does it Matter?
Well, so I ran a little benchmark, which is iffy all over the place, but here's the 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");
}
}
}
使用 NSQUARED:
With 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
使用哈希集
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 获胜！
但仅差一点点... .15ms 就在 currentTimeMillis() 的误差范围内，而且我的基准测试中有一些大漏洞.请注意，对于任何长度超过 100000 的列表，您可以简单地返回 true 因为会有重复.事实上，如果列表是随机的，您可以为更短的列表返回真正的 WHP.什么是道德?在极限情况下，最有效的实现是:
BITSET Wins!
But only by a hair... .15ms is within the error for currentTimeMillis(), and there are some gaping holes in my benchmark. Note that for any list longer than 100000, you can simply return true because there will be a duplicate. In fact, if the list is anything like random, you can return true WHP for a much shorter list. What's the moral? In the limit, the most efficient implementation is:
return true;
而且你不会经常犯错.
这篇关于Java 数组，查找重复项的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
