首页 > 试题广场 >

给定两个排好序的数组,怎样高效地判断这两个数组中是否存在相同

[问答题]

给定两个排好序的数组,怎样高效地判断这两个数组中是否存在相同的数字?不妨设函数原型为: bool findCommon(int a[],int size_a,int b[],int size_b); 撰写源码并说明时间复杂度。

排好序应该是升序吧,复杂度O(size_a+size_b) boolean findCommon(int a[],int size_a,int b[],int size_b){
        boolean res=false;
        if(size_a<=0||size_b<=0)
            return res;
        int i=0,j=0;
        while(i<size_a&&j<size_b)
        {
            if(a[i]==b[j]){
                res=true;
                break;
            }
            if(a[i]<b[j])
                i++;
            else
                j++;
        }
        return res;
    }

编辑于 2017-02-16 13:48:56 回复(0)