两个已排序List求交集

来源:百度知道 编辑:UC知道 时间:2024/06/14 16:18:19
给定两个已排序的整型列表List<Integer> List0与List1,求出其交集,要求速度最快,额外占用空间最少的算法?<java>

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));
}
}
}

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)//c