數(shù)組求交集的方法
1.暴力搜索
2.利用HashMap
3.先排序再用兩個(gè)指針查找
4.位圖法
5.大文件求交集用分治法，組內(nèi)用位圖法
public class Main {
/**
* 暴力搜索
* <p>
* 時(shí)間復(fù)雜度O(n^2) 空間復(fù)雜度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>
* 時(shí)間復(fù)雜度O(n) 空間復(fù)雜度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);
}
/**
* 先排序再用兩個(gè)指針查找
* <p>
* 時(shí)間復(fù)雜度O(nlogn) 空間復(fù)雜度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);
}
/**
* 位圖法
* 思路：
* 假設(shè)數(shù)組a有m個(gè)元素，數(shù)組b有n個(gè)元素，并且滿足m<n
* 1.建立一個(gè)int數(shù)組 extra 來(lái)表示bitmap, 一個(gè)int為32位，可以表示32個(gè)數(shù), 那么extra的元素個(gè)數(shù)為: Max(a)-Min(a) + 1
* 2.將a中的元素映射到 extra 中的對(duì)應(yīng)位置，用1表示
* 3.將b中的元素映射到 extra 中的對(duì)應(yīng)位置，如果該位置已經(jīng)是1，說(shuō)明元素已經(jīng)存在，為重復(fù)元素，記錄該元素
* <p>
* 時(shí)間復(fù)雜度O(n) 空間復(fù)雜度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; //存儲(chǔ)差值要gap個(gè)int 類型的數(shù)
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中位置, 用位運(yùn)算將該位置記為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元素的范圍，肯定就不重復(fù)了，所以只關(guān)注ps數(shù)組最大最小值范圍內(nèi)的數(shù)
if (pl[i] >= min && pl[i] <= max) {
row = (pl[i] - min) / 32;
column = (pl[i] - min) % 32;
//如果該位置已經(jīng)是1，說(shuō)明元素已經(jīng)存在，為重復(fù)元素，記錄該元素
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();
}
}
