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

搜集的面试题目

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

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