有两个集合，两个集合都是10万个数据(已排序)，判断B是不是A的子集，算法时间复杂度为Q（N）...

 有两个集合   集合A{1，7，19，21，55，100。。。}   集合B{7，22，100。。。}   两个集合都是10万个数据(已排序)，要求写一个算法，判断B是不是A的子集，算法时间复杂度为Q（N） #include <iostream>
using namespace std;
//b是否是a的子集
bool isSubUnion(int a[],int b[],int lenA,int lenB)
{
    int i=0,j=0;
    while(i<lenB&&j<lenA)
    {
        if(b[i]<a[j])
        {
            return false;
        }
        else if(b[i]>a[j])
        {
            j++;

        }
        else 
        {
            i++;
            j++;
        }
    }
    if(i==lenB)
    {
        return true;
    }
    else
    {
        return false;
    }
    
    return true;
}
int main(int argc, _TCHAR* argv[])
{
    int a[]={1,2,3,4,5,9,11,12,13,15};
    int b[]={1,4,11,13};
    cout<<isSubUnion(a,b,sizeof(a)/sizeof(int),sizeof(b)/sizeof(int));
    return 0;
}

转载于:https://www.cnblogs.com/zhuxiongfeng/archive/2010/03/28/1699021.html

总结

以上是生活随笔为你收集整理的有两个集合，两个集合都是10万个数据(已排序)，判断B是不是A的子集，算法时间复杂度为Q（N）...的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。