一道笔试题（创新工厂）

有两个长度分别为m,n的非降序整型数组，其中n>m*m,求这两个数组的交集，要求复杂度尽可能低。

 

如数组a:-1,4,5

数组b:-15，1，3，4，5，7，8，9，10，15

结果应该是：4，5

 

题目大概就是这样，欢迎大家练手，并把结果发上来讨论，我也会尽快贴上我的代码~~

 

 

昨天比较忙，没时间上来看。刚看了下大家的回贴，对一些疑惑做一下回复吧：

1.卷子中写的是就是“非降序”，我的理解应该是递增数组，但允许重复！

2.楼下的很多方法都可行，但很多没考虑到n>m*m这一个条件，也许m=3,n=1000呢。。在这种情况下应该如果减少复杂度？

 题目看似简单，只求结果，相信大家都会，关键是如何最高效的得到结果。

1: 数组-> Set
2: 两个set求交集。

先排序，之后每个数组循环一次即可得到结果。

Set aSet=new HashSet() ;
Set bSet=new HashSet() ;
for(int i=0 ;i<n;i++)
    aSet.add(A[i]) ;
for(int i=0 ;i<m;i++)
    bSet.add(B[i]) ;
aSet.retainAll(bSet) ;
for(Integer i:aSet)
   System.out.println(i) ;
  

Integer[] aa={-1,4,5};
    	Integer[] ab={-15,1,3,4,5,7,8,9,10,15};
    	List<Integer> lista = Arrays.asList(aa);  
    	List<Integer> listb=Arrays.asList(ab);
    	List<Integer> listc=new ArrayList<Integer>();
    	listc.addAll(listb);
    	listc.retainAll(lista);
    	System.out.println(listc);

由于已经是排序好的，同时循环两个数组。
同步对比。

a = (-1,4,5)
b = (-15,1,3,4,5,7,8,9,10,15)
res=[]
i=len(a)-1
j=len(b)-1
while(i>=0 and j>=0):
    while(a[i]>b[j] and i>=0):  
        #print '%s<%s'%(a[i],b[j])
        i-=1
    while(b[j]>a[i] and j>=0):
        #print '%s<%s--'%(b[j],a[i])
        j-=1

    if(a[i]==b[j] and not a[i] in res):
        res.append(a[i])
        i-=1
        j-=1
res.reverse()
print res

貌似有类似帖，说是求两个列表中相同的值

import java.util.ArrayList;
import java.util.List;

public class Test {

/**
* @param args
*/
public static void main(String[] args) {

Test t  =  new Test();
int[] a={1,4,5,67,8,78};
int[] b={1,4,5,67,8,78,1,4,5,67,8,78,1,4,5,67,8,78,1,4,5,67,8,78,1,4,5,67,8,78,1,4,5,67,8,78};

for(int i=0;i<t.test1(a, b).size();i++){
System.out.print(t.test1(a, b).get(i)+",");
}
}
@SuppressWarnings("unchecked")
public List test1(int[]a,int[]b){
List c = new ArrayList();

for(int i=0;i<a.length;i++){
for(int j=0;j<b.length;j++){
if(a[i] == b[j]&&!c.contains(a[i])){
c.add(a[i]);
}
}
}
return c;
}

}

如果数组元素不重复并且已排序。最好的办法应该是初始化俩指针遍历两个数组的方法（参考IR导论前面几章中提到的求交集的方法），具体做法是：
先初始化两个指针分别指向数组的开始。
比较当前指针指向的俩个元素，如果指针2的元素大于指针1，则移动指针1，如果指针1指向的元素大于指针2，则移动指针2，如果相等则保存结果然后俩指针同时向前移动。如此重复到读取完两个数组的元素。此方法需要遍历两个数组，用Set方法需要遍历两个数组而且需要对元素做hash运算+比较，效率没有上诉算法快。
但本题中有一个关键词是“非递减”。不知道在这里是甚么意思，望LZ告知

数字会不会很多？
将数组a插入a表
将数组b插入b表
select * from a
intersect
select * from b
哈哈，会不会复杂度很高？