求两个数组的交集

场景：怎么求两个数组的交集

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

------解决方案--------------------
其实解决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++;
}
}

------解决方案--------------------

探讨
既然是排序好的,
那么可以直接对比a和b的元素
i,j是a,b中元素的当前位置
Java codewhile(i<a.length&& j< b.length)
{if(a[i]< b[j])
{
i++;
}elseif (a[i]== b[j])
{
输出这个元素;
i++;
j++;
}else
{
j++;
}
}

------解决方案--------------------
偷懒的写法：

Java code


int[] a = {1,5,8,10,14,15,17,18,20,22,24,25,28};
int[] b = {2,4,6,8,10,12};

List   list   =   new   ArrayList(Arrays.asList(a));   
list.retainAll(Arrays.asList(b));   //   list   中的就是交集了.

------解决方案--------------------
代码如下，如果你想降低时间复杂度，可以在getDuplicated方法里多加判断，因为是排过序的，当第二个数组的元素大小超过了第一个数组的最后一个值的时候，就没有必要继续了；还有当前元素如果小于第一个数组的第一个元素是，也没必要继续，直接跳到下一次循环。等等...

Java code

import java.util.*;

public class STest {
    private static int count, index;
    
    public static void getDuplicated(int[] a, int[] b){
        Set<Integer> set = new LinkedHashSet<Integer>();
        
        for(int i=0; i<a.length; i++)
            set.add(a[i]);
        
        for(int j=0; j<b.length; j++){
            int setSize = set.size();
            
            if(j>0){
                if(b[j] == b[j-1])
                    continue;
            }
            
            set.add(b[j]);
            
            if(set.size() == setSize){
                b[index] = b[j];
                count ++;
                index ++;
            }
        }
    }
    
    public static void main(String[] args) {
        int[] first = {1,5,8,8,10,100,14,15,70,70,17,18,18,20,22,24,25,28};
        int[] second = {2,4,4,4,4,6,8,8,8,8,10,12};
        
        getDuplicated(first, second);
        
        for(int i=0; i<count; i++)
            System.out.print(second[i] +" ");
    }
}

------解决方案--------------------
高效率的上面都说了，我写个低效率的，优点在于没用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;
            }
        }
    }
}

------解决方案--------------------
知道散列集HashSet 吗，它在数据组织上类似于数学上的数组，可以进行“交”、“并”、“差”等运算。
例如：
  Integer  one=new Integer(1),
         two=new Integer(2),
         three=new Integer(3),
         four=new Integer(4),
         five=new Integer(5),
         six=new Integer(6);
  HashSet A=new HashSet(),
        B=new HashSet(),
        tempSet=new HashSet();
  A.add(one);  
  A.add(two);
  A.add(three);
  A.add(four);
  B.add(one);
  B.add(two);
  B.add(five);
  B.add(six);
  tempSet=(HashSet)A.clone();
  A.removeAll(B);        //A变成调用该方法之前的A集合与B集合的差集
 B.removeAll(tempSet);  //B变成调用该方法之前的B集合与tempSet集合的差集
 B.addAll(A);           //B就是最初的A与B的交集

相关推荐