我觉得下边的代码更公平一些。
Sort used time (ms): 4657
HashMap Used time (ms): 1696
HashSet Used time (ms): 2433
public class test {
public int v1(Integer[] in) {
Integer[] a = new Integer[in.length];
System.arraycopy(in, 0, a, 0, in.length);
if (a.length == 0)
return 0;
Arrays.sort(a);
int ret = 1;
int start = 0;
int dup = 0;
for (int i = 1; i < a.length; i++) {
if (a[i] == a[i - 1] + 1) {
ret = Math.max(ret, i - start - dup + 1);
} else if (a[i] == a[i - 1]) {
dup += 1;
} else {
start = i;
dup = 0;
}
}
return ret;
}
public int v2(Integer[] a) {
HashMap map = new HashMap();
int max = 1;
for (int i : a) {
if (map.containsKey(i))
continue;
map.put(i, 1);
if (map.containsKey(i - 1)) {
max = Math.max(max, merge(map, i - 1, i));
}
if (map.containsKey(i + 1)) {
max = Math.max(max, merge(map, i, i + 1));
}
}
return max;
}
private int merge(HashMap map, int left, int right) {
int upper = right + map.get(right) - 1;
int lower = left - map.get(left) + 1;
int len = upper - lower + 1;
map.put(upper, len);
map.put(lower, len);
return len;
}
public int v3(Integer[] num) {
Set hs = new HashSet(Arrays.asList(num));
int ans = 0;
for (int v : num)
if (hs.contains(v))
ans = Math.max(ans, getCount(hs, v, false) + getCount(hs, v + 1,
true));
return ans;
}
int getCount(Set hs, int v, boolean asc) {
int count = 0;
while (hs.contains(v)) {
hs.remove(v);
count++;
if (asc)
v++;
else
v--;
}
return count;
}
public void run() {
Integer MAX_RANDOM = 327670;
Integer[][] ar = new Integer[1][10000000];
Random rand=new Random();
for (int i = 0; i < ar.length; i++) {
for (int j = 0; j < ar[i].length; j++) {
ar[i][j] = rand.nextInt()%MAX_RANDOM;
}
}
long milli = System.currentTimeMillis();
for (int i = 0; i < ar.length; i++) {
v1(ar[i]);
}
long used = System.currentTimeMillis() - milli;
System.out.println("Sort used time (ms): " + used);
milli = System.currentTimeMillis();
for (int i = 0; i < ar.length; i++) {
v2(ar[i]);
}
used = System.currentTimeMillis() - milli;
System.out.println("HashMap Used time (ms): " + used);
milli = System.currentTimeMillis();
for (int i = 0; i < ar.length; i++) {
v3(ar[i]);
}
used = System.currentTimeMillis() - milli;
System.out.println("HashSet Used time (ms): " + used);
}
public static void main(String[] args) throws Exception
{
new test().run();
}
}
