求两个有序整数集合的交集

  |   0 评论   |   986 浏览

搜集的面试题目

求两个有序整数集合的交集


import java.util.HashSet;
import java.util.Set;

/**
* 求两个有序整数集合的交集
*
* @author Administrator
*
*/
public class NumberCollectionCrossTest {

/**
 * 利用set元素不重复的特性
 * 
 * @param a
 * @param b
 * @return
 */
private static Set<Integer> setMethod(int[] a, int[] b) {
	Set<Integer> setA = new HashSet<>();
	Set<Integer> 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<Integer> whlieMethod(int[] a, int[] b) {
	Set<Integer> 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<Integer> 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

648ac377gy1fcmr6wunruj20cr0k040u.png

评论

发表评论