搜集的面试题目
求两个有序整数集合的交集
import java.util.HashSet;
import java.util.Set;
/**
* 求两个有序整数集合的交集
*
* @author Administrator
*
*/
public class NumberCollectionCrossTest {
/**
* 利用set元素不重复的特性
*
* @param a
* @param b
* @return
*/
private static Set setMethod(int[] a, int[] b) {
Set setA = new HashSet<>();
Set setB = new HashSet<>();
for (int i = 0; i < a.length; i++) {
setA.add(a[i]);
}
for (int i = 0; i < b.length; i++) {
if (!setA.add(b[i])) {
setB.add(b[i]);
}
}
return setB;
}
/**
* 使用while循环比较
*
* @param a
* @param b
* @return
*/
private static Set whlieMethod(int[] a, int[] b) {
Set setA = new HashSet<>();
int i = 0, j = 0;
while (i < a.length && j < b.length) {
if (a[i] < b[j]) {
i++;
} else if (a[i] > b[j]) {
j++;
} else {
setA.add(a[i]);
i++;
j++;
}
}
return setA;
}
private static int[] intersect(int[] a, int[] b) {
if (a[0] > b[b.length - 1] || b[0] > a[a.length - 1]) { // 不存在交集
return new int[0];
}
int[] intersection = new int[Math.min(a.length, b.length)];
int offset = 0;
for (int i = 0, s = i; i < a.length && s < b.length; i++) {
while (a[i] > b[s]) {
s++;
}
if (a[i] == b[s]) {
intersection[offset++] = b[s++];
// System.out.println(offset);
}
while (i < (a.length - 1) && a[i] == a[i + 1]) { // 去掉相同值
i++;
}
}
if (intersection.length == offset) {
return intersection;
}
int[] duplicate = new int[offset];
System.arraycopy(intersection, 0, duplicate, 0, offset);
return duplicate;
}
public static void main(String[] args) {
// init
int[] a = new int[2000000];
int[] b = new int[1000000];
for (int i = 0; i < a.length; i++) {
a[i] = i + 20;
}
for (int i = 0; i < b.length; i++) {
b[i] = i + 10;
}
// start
long begin = System.currentTimeMillis();
Set set = setMethod(a, b);
long end = System.currentTimeMillis();
System.out.println("setMethod 耗时:" + (end - begin) + ", size:"
+ set.size());
begin = System.currentTimeMillis();
set = whlieMethod(a, b);
end = System.currentTimeMillis();
System.out.println("whlieMethod 耗时:" + (end - begin) + ", size:"
+ set.size());
begin = System.currentTimeMillis();
int[] c = intersect(a, b);
end = System.currentTimeMillis();
System.out.println("intersect 耗时:" + (end - begin) + ", size:"
+ c.length);
}
}
打印结果:
setMethod 耗时:1565, size:999990
whlieMethod 耗时:1150, size:999990
intersect 耗时:16, size:999990
评论区