至顶网›软件频道 ›如何求两个数组的交集？

如何求两个数组的交集？

扫一扫
分享文章到微信
扫一扫
关注官方公众号
至顶头条

如何求两个数组的交集？

作者：csdn 来源：csdn 2009年12月17日

如何求两个数组的交集？

有两个数组a{1,5,8,10,14,15,17,18,20,22,24,25,28}和b{2,4,6,8,10,12}，如何求出他们之间的交集？要求效率越高越好
注：数组都是从小到大排序好的.

首先确定好单独的数组有无重复的，如果没有，可以先把一个数组放到set中去，比如把a放到set中去，再遍历b数组放到set中去，如果set的size没有变化，那么b中的这个元素就是重复元素，也就是所谓的交集。上面这个算法有没有排过序都可以做但是有一点需要注意：比如我把a加到数组中，其实a中有无重复的不要紧，但是如果b中有重复的，比如有2个100，但是100恰好又不在a中，这样的情况下，上面的算法就会把100当做a和b交集的一部分，所以要避免这种情况。其实解决b中的重复也很简单，只要在遍历b的时候，判断一下当前的这个元素是否和前面的元素一样，如果一样，那就continue执行下一次循环。
所以总结起来看，在这个算法中，如果a是第一个放到set中去的话，那么a有没有排序无所谓；但是为了避免麻烦，b最好是排序的。

既然是排序好的,
那么可以直接对比a和b的元素
i,j是a,b中元素的当前位置

Java code

while(i<a.length && j < b.length)
{
if(a[i] < b[j])
{
    i++;
}
else if (a[i] == b[j])
{
    输出这个元素;
    i++;
    j++;
}
else
{
    j++;
}
}

 
高效率的上面都说了，我写个低效率的，优点在于没用API中现成的方法，笔试时经常碰到这种变态要求。。。 
Java code 

public class TestUnion {
    public static void main(String args[]){
        int a[] = {1,5,8,10,14,15,17,18,20,22,24,25,28};
        int b[] = {2,4,6,8,10,12};
        for(int i = 0; i < b.length; i++){
            for(int j = 0; j < a.length; j++){
                if(b[i] == a[j]){
                    System.out.print(" " + b[i]);
                    break;
                }
                else
                    continue;
            }
        }
    }
}

如何求两个数组的交集？

业界热点: