2个数组的交集算法

今天在做项目的时候要用到2个数据的交集算法，就去研究了一下。

原本考虑的情况是2个数组都是升序且无重复元素，所以就用了以下算法：

public static List isRepeat(int list1[], int list2[]) {
	if (list1 != null && list2 != null) {
		int length1 = list1.length;
		int length2 = list2.length;
		List rep = new ArrayList();
		int i = 0, j = 0;
   		while (i < length1 && j < length2) {
    			if (list1[i] == list2[j]) {
     				rep.add(new Integer(list1[i]));
     				i++;
     				j++;
    			} else if (list1[i] > list2[j]) {
     				j++;
    			} else {
    				i++;
    			}
   		}return rep;
	}
	return null;
}

 

后来发现数据在数据库中是以varchar形式存在，无法以order by正确排序，心想如果自己先排序再用以上算法有点不值。于是乎继续研究，发现用List.retianAll()方法就可以实现，代码如下：

List list = new ArrayList(Arrays.asList(a));
list.retainAll(Arrays.asList(b));

 

这个方法唯一的遗憾就是，如果数组中存在相同的元素，该方法不会过滤掉。

 

评论

2 楼 fenglingxuewqk 2010-10-13  

ah_fu 写道

你的算法是错的！
关键就在else{i++;}的部分。
当左边总是小于右边的时候，连续两次i++会导致跳过一个元素不比较

恩 是的 应该把else{i++;}去掉。另外我又仔细看了下 发现这个算法还是有其他BUG的。。。

1 楼 ah_fu 2010-09-27  

你的算法是错的！
关键就在else{i++;}的部分。
当左边总是小于右边的时候，连续两次i++会导致跳过一个元素不比较