检查两个元素在C中是否具有公共元素

发布时间：2020-12-16 09:55:17 所属栏目：百科来源：网络整理

导读：我希望函数在两个向量之间存在任何元素匹配时返回true, 注意：我的矢量没有排序以下是我的源代码, bool CheckCommon( std::vector long inVectorA,std::vector long inVectorB ){ std::vector long *lower,*higher; size_t sizeL = 0,sizeH = 0; if( inVect

我希望函数在两个向量之间存在任何元素匹配时返回true,

注意：我的矢量没有排序
以下是我的源代码,

bool CheckCommon( std::vector< long > &inVectorA,std::vector< long > &inVectorB )
{
    std::vector< long > *lower,*higher;

    size_t sizeL = 0,sizeH = 0;

    if( inVectorA.size() > inVectorB.size() )
    {
        lower = &inVectorA;
        sizeL = inVectorA.size();
        higher = &inVectorB;
        sizeH = inVectorB.size();
    }
    else
    {
        lower = &inVectorB;
        sizeL = inVectorB.size();
        higher = &inVectorA;
        sizeH = inVectorA.size();
    }

    size_t indexL = 0,indexH = 0;

    for( ; indexH < sizeH; indexH++ )
    {
        bool exists = std::binary_search( lower->begin(),lower->end(),higher->at(indexH) );

        if( exists == true )
            return true;
        else
            continue;
    }
    return false;
}

当矢量B的大小小于矢量A的大小时,这工作正常,但是当矢量B的大小大于矢量A的大小时,即使存在匹配也返回假.

解决方法

发布代码的问题在于,当向量未排序时,不应使用std :: binary_search.仅针对排序范围定义行为.

如果输入向量未排序,则可以使用find_first_of检查是否存在找到的第一个公共元素.

bool CheckCommon(std::vector<long> const& inVectorA,std::vector<long> const& nVectorB)
{
    return std::find_first_of (inVectorA.begin(),inVectorA.end(),nVectorB.begin(),nVectorB.end()) != inVectorA.end();
}

inVectorA.size()* inVectorB.size();中find_first_of的复杂性达到线性.它会比较元素直到找到匹配项.

如果你想修复原始算法,那么你可以复制一个向量和std :: sort它,然后std :: binary_search可以使用它.

在容器之间进行大量此类匹配的实际程序中,容器通常保持分类.然后,inVectorA.size()inVectorB.size()中搜索的复杂性达到线性.

std :: find_first_of比排序两个范围更有效,然后当两个范围相当短或第二个范围短于第一个范围长度的二进制对数时搜索匹配.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!