关于算法问题，请大家帮忙看一下，很急！！

Question

两个已排序的整型数组，求交集，最快算法
输入：两个已排序的整型数组（int a[m], b[n]）
输出：两个数组的交集

Answer 1

老掉牙的面试题了
1，直接归并，复杂度m+n
2，hash，复杂度m+n
3, 二分另一个 复杂度mlogn 或 nlogm，m、n相差较大时这种方法比前两种好。

Answer 2

                List<Integer> results = new ArrayList<Integer>();
int i = 0;
int k = 0;
while (i < a.length && k < b.length) {
if (a[i] == b[k]) {
results.add(a[i]);
i++;
k++;
} else if (a[i] < b[k]) {
i++;
} else {
k++;
}
}

Answer 3

写了个，应该满足了，4楼的只满足长度相同的2个数组
import java.util.*;
class Array_test 
{
public static int a[]={1,5,7,9,14,18,20,25,28,30};
public static int b[]={2,4,7,10,14,20,25};
public static int c[]=new int[10];
public static void main(String[] args) 
{
int i=0;
int j=0;
int m=0;
while(i<copmCount(a,b)&&j<copmCount(a,b)){
if(a[i]<b[j]){
i++;
}else if(a[i]>b[j]){
j++;
}else{
c[m]=a[i];
m++;
i++;
j++;
while((i<a.length&&j<b.length)&&same(a[i],b[j])){
c[m]=a[i];
i++;
j++;
}
}
System.out.println(i+":"+j);

}
System.out.println(Arrays.toString(c));
} public static int copmCount(int[] x,int[] y){
return x.length<y.length?x.length:y.length; }
public static boolean same(int x,int y){
return x==y;
}
}

Answer 4

我怎么觉得ls的“4楼的只满足长度相同的2个数组”这句话纯属在胡扯………………
明显4楼的代码已经满足了lz的需求

Answer 5

    public static void main(String[] args)
    {
        int[]a={1,14,5,7};
        int[]b={1,15,7,5};
        Set set=new HashSet();
        for(int i=0;i<a.length;i++)
        {
            set.add(a[i]);
        }
        for(int i=0;i<b.length;i++)
        {
            if(!set.add(b[i]))
                System.out.println(b[i]);
        }
    }

Answer 6

的确，4楼的基本满足了
我在while里面的判断没有4楼精简

Answer 7

这个写的不赖，还有一个效率比较低的，用两个for循环。。呵呵

Answer 8

给你一个效率很高的
    long start=System.nanoTime();
    int[] a=new int[]{1,5,7,9,14,18,20,25,28,30};
    BitSet bt=new BitSet();
    for(int i=0;i<a.length;i++)
     bt.set(a[i]);
    int []bb=new int[]{2,4,7,10,14,20,25};
    BitSet bt2=new BitSet();
    for(int I: bb)
     bt2.set(I);
    bt.and(bt2);
    System.out.println(bt);
    System.out.println(System.nanoTime()-start);

Answer 9

  闲的无聊，就说的详细点：   1， 归并算法，即利用归并排序的思路求交集。
       因为两个序列有序，所以可在 m+n的复杂度内获取结果。
       ----最通俗的方法，有数据结构基础的人应该都能很快相出的方法。    2， hash A数组，然后用B数组的元素查这个hash表，判断有没有同时在A中存在。
       假定hash桶比较大、冲突较少，可以逼近 m+n 复杂度解决。
        不过这个算法没有用到两个数组有序，显然不是最优。   3， 假定A 数组只有两个元素， B数组10亿个，那么用A数组的元素去在B数组中二分查找，可以log(size(b)) 复杂度内判断该数是否在B中存在。 可在 size(A)log(size(B)) 或 size(B)log(size(A)) 内解决。    具体写程序要先判断 (m+n), nlogM, mlogn 那个最小，然后选择相应的算法。。
     ps：
          合在一起排序，真是个绝顶搜注意，弄出来个(m+n)log(m+n)的复杂度。
           如果我是考官，都要Orz你了。。

Answer 10

可不可以用java的api的,可以的话直接用set类啦,超级容易