Question

两个已排序List求交集

给定两个已排序的整型列表List<Integer> List0与List1，求出其交集，要求速度最快，额外占用空间最少的算法？<java>

Answer 1

public List<Integer> listCross(List<Integer> list0,List<Integer> list1)
{
//先遍历size小的list每个元素（这个list设为la 另一个lb），遍历时与另个list中元素比较，找到相同的元素，因为是排序的，假设为升序。la中每下一个元素都不必与lb的第一个开始比较，而是接着上个元素比较完之后的剩余元素直至相同
List<Integer> la=list0;
List<Integer> lb=list1;
List<Integer> lc=new ArrayList<Integer>();
int a=list0.size();
int b=list1.size();
int bs=b;//size of the longer list
if(a>b){
la=list1;lb=list0;
bs=a;
}
int c=0;//与lb中哪个元素开始比较

for(Integer i:la)
{
for(int k=c;k<bs;k++)
{
if(lb.get(k)>i)break;//lb.get(k)大于i 则lb的下一个元素也只会比i大所以
//就不用再执行了
if(lb.get(k)==i)//cross
{
c=k+1; //这个地方比较重要，lb中下次就c以前的就不用比较 了
lc.add(i);
break;
}//if
}//for
}//for
return lc;
}

Answer 2

for(int i =0 ;i < list0.length;i++){
for(int j =0 ; j< list1.length;j++){
if(list0.get(i)<list1.get(j)) break;
else{
if(list0.get(i)=list1.get(j)) System.out.print(list0.get(i));
}
}
}