数组求交集的方法
1.暴力搜索
2.利用HashMap
3.先排序再用两个指针查找
4.位图法
5.大文件求交集用分治法，组内用位图法
public class Main {
/**
* 暴力搜索
* <p>
* 时间复杂度O(n^2) 空间复杂度O(1)
*/
static ArrayList<Integer> f0(int[] arr, int[] arr2) {
Set<Integer> res = new HashSet<>();
for (int i : arr) {
for (int j : arr2) {
if (i == j) {
res.add(i);
}
}
}
return new ArrayList<>(res);
}
/**
* 利用HashMap
* <p>
* 时间复杂度O(n) 空间复杂度O(n)
*/
static ArrayList<Integer> f1(int[] arr, int[] arr2) {
Set<Integer> res = new HashSet<>();
Map<Integer, Integer> map = new HashMap<>();
for (int a : arr) {
if (map.containsKey(a)) {
map.put(a, (map.get(a) + 1));
} else {
map.put(a, 1);
}
}
for (int a : arr2) {
if (map.containsKey(a)) {
res.add(a);
}
}
return new ArrayList<>(res);
}
/**
* 先排序再用两个指针查找
* <p>
* 时间复杂度O(nlogn) 空间复杂度O(1)
*/
static ArrayList<Integer> f2(int[] arr, int[] arr2) {
Set<Integer> res = new HashSet<>();
int p = 0, q = 0;
Arrays.sort(arr);
Arrays.sort(arr2);
while (p < arr.length && q < arr2.length) {
if (arr[p] < arr2[q]) {
p++;
} else if (arr2[q] < arr[p]) {
q++;
} else {
res.add(arr[p]);
p++;
q++;
}
}
return new ArrayList<>(res);
}
/**
* 位图法
* 思路：
* 假设数组a有m个元素，数组b有n个元素，并且满足m<n
* 1.建立一个int数组 extra 来表示bitmap, 一个int为32位，可以表示32个数, 那么extra的元素个数为: Max(a)-Min(a) + 1
* 2.将a中的元素映射到 extra 中的对应位置，用1表示
* 3.将b中的元素映射到 extra 中的对应位置，如果该位置已经是1，说明元素已经存在，为重复元素，记录该元素
* <p>
* 时间复杂度O(n) 空间复杂度O(Max(a)-Min(a)/32)
*/
static List<Integer> f3(int[] a, int[] b) {
int min, max;
int alen = a.length;
int blen = b.length;
int[] ps, pl;
int len;
int longlen;
if (alen < blen) {
ps = a;
len = alen;
longlen = blen;
pl = b;
} else {
ps = b;
len = blen;
longlen = alen;
pl = a;
}
min = max = ps[0];
for (int i = 1; i < len; ++i) {
if (ps[i] < min)
min = ps[i];
if (ps[i] > max)
max = ps[i];
}
int gap = max - min;
gap = gap / 32 + 1; //存储差值要gap个int 类型的数
int[] extra = new int[gap];
for (int i = 0; i < gap; ++i) extra[i] = 0;
int row, column;
for (int i = 0; i < len; ++i) {
//找到 ps[i] 在bitmap中位置, 用位运算将该位置记为1
row = (ps[i] - min) / 32;
column = (ps[i] - min) % 32;
extra[row] |= 1 << column;
}
Set<Integer> res = new HashSet<>();
for (int i = 0; i < longlen; ++i) {
//pl[i]如果超出ps元素的范围，肯定就不重复了，所以只关注ps数组最大最小值范围内的数
if (pl[i] >= min && pl[i] <= max) {
row = (pl[i] - min) / 32;
column = (pl[i] - min) % 32;
//如果该位置已经是1，说明元素已经存在，为重复元素，记录该元素
if (0 != (extra[row] & (1 << column))) {
res.add(pl[i]);
}
}
}
return new ArrayList<>(res);
}
public static void main(String[] args) {
Random random = new Random();
int m = 100000;
int[] a = new int[m];
while (m > 0) {
a[m - 1] = random.nextInt(5000);
m--;
}
int n = 100000;
int[] b = new int[n];
while (n > 0) {
b[n - 1] = random.nextInt(5000);
n--;
}
new Thread(() -> {
long time = System.currentTimeMillis();
System.out.println(f0(a, b));
System.out.println("f0 cost: " + (System.currentTimeMillis() - time) + " ms");
}).start();
new Thread(() -> {
long time = System.currentTimeMillis();
System.out.println(f1(a, b));
System.out.println("f1 cost: " + (System.currentTimeMillis() - time) + " ms");
}).start();
new Thread(() -> {
long time = System.currentTimeMillis();
System.out.println(f2(a, b));
System.out.println("f2 cost: " + (System.currentTimeMillis() - time) + " ms");
}).start();
new Thread(() -> {
long time = System.currentTimeMillis();
System.out.println(f3(a, b));
System.out.println("f3 cost: " + (System.currentTimeMillis() - time) + " ms");
}).start();
}
}
