在一个不重复的数组中,统计有多少组两个元素相加得0。
这里使用三种方式实现,并统计他们各自花费的时间:
import java.util.Arrays;
import java.util.HashMap;
import java.util.Random; public class TwoSum {
private static int N = 100000;
private static int[] a = new int[N];
private static Random random = new Random();
private static HashMap<Integer, Boolean> m = new HashMap<Integer, Boolean>(); private int binarySearch(int[] a, int num) {
int low = 0, mid = 0, high = a.length - 1;
while (low <= high) {
mid = low + (high - low) / 2;
if (a[mid] > num) {
high = mid - 1;
} else if (a[mid] < num) {
low = mid + 1;
} else {
return mid;
}
} return -1;
} public int solution1() {
int count = 0;
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) {
if (a[i] + a[j] == 0) {
count++;
}
}
}
return count;
} public int solution2() {
int count = 0;
Arrays.sort(a);
for (int i = 0; i < N; i++) {
if (binarySearch(a, -a[i]) > i) {
count++;
}
}
return count;
} public int solution3() {
int count = 0;
for (int i = 0; i < N; i++) {
if (m.containsKey(-a[i])) {
count++;
}
}
return count / 2;
} public static int uniform(int N) {
if (N <= 0) throw new IllegalArgumentException("Parameter N must be positive");
return random.nextInt(N);
} public int uniform(int a, int b) {
if (b <= a) throw new IllegalArgumentException("Invalid range");
if ((long) b - a >= Integer.MAX_VALUE) throw new IllegalArgumentException("Invalid range");
return a + uniform(b - a);
} public static void main(String[] args) {
TwoSum ts = new TwoSum();
int count = 0;
int rand = 0;
int i = 0;
boolean flag = true; while (i < a.length) {
rand = ts.uniform(-10000000, 10000000);
flag = true;
for (int j = 0; j < a.length; j++) {
if (a[j] == rand) {
flag = false;
break;
}
}
if (flag) {
a[i] = rand;
i++;
//System.out.println(rand + " " + flag);
}
} for (int j = 0; j < N; j++) {
m.put(a[j], true);
} Stopwatch timer1 = new Stopwatch();
count = ts.solution1();
double time = timer1.elapsedTime();
System.out.println("count1: " + count + " cost1: " + time); count = 0;
time = 0;
Stopwatch timer2 = new Stopwatch();
count = ts.solution2();
time = timer2.elapsedTime();
System.out.println("count2: " + count + " cost2: " + time); count = 0;
time = 0;
Stopwatch timer3 = new Stopwatch();
count = ts.solution3();
time = timer3.elapsedTime();
System.out.println("count3: " + count + " cost3: " + time);
}
}
solution1:直接使用一个两层for循环,所以最终的时间复杂度为O(N^2);
solution2:先将数组排序,然后通过二分查找来搜索数组中每个元素的相反数,此时的时间复杂度为O(N*log(N));
solution3:和方法一类似,只不过是通过哈希表中查找元素的复杂度为O(1)来优化搜索时间,此时时间复杂度为O(N);
当N=1000时 count1: 0 cost1: 0.004
count2: 0 cost2: 0.002
count3: 0 cost3: 0.001 当N=10000时 count1: 5 cost1: 0.026
count2: 5 cost2: 0.009
count3: 5 cost3: 0.005 当N=100000时 count1: 238 cost1: 2.296
count2: 238 cost2: 0.077
count3: 238 cost3: 0.012
这里因为产生不重复的随机数使用的是最简单的两层循环,所以当数组的length太大时,比如1000000时,在产生随机数的过程中会消耗很长时间,这一部分可以使用其他更优的方法实现。