假设有容器A和容器B…已知A里面有m个元素,且元素无重复,B里面有n个元素,且元素全部来自于A,并且n小于等于m…

求:将B内的元素按照A里面的顺序排序…

示例:

假设:A = { 5, 3, 6, 4, 1, 8 }; B = { 1, 3, 8, 4};

排序后,应该为:B= { 3, 4, 1, 8 };

解决方案示意代码如下:

我给出的解决方案:

void Test23_1(const vector<int> &vecSourse, vector<int> &vecData)
{
    std::vector<int> vecTmp;
    for (vector<int>::const_iterator itr = vecSourse.begin(); itr != vecSourse.end(); ++itr)
    {
        if(vecData.end() != std::find(vecData.begin(), vecData.end(), *itr))
            vecTmp.push_back(*itr);
    }
    vecData = vecTmp;
}

我感觉我的复杂度是:m*log(n)

同事给出的方案:

void Test23_2(const vector<int> &vecSourse, vector<int> &vecData)
{
    std::vector<int> vecTmp1 = vecSourse;
    std::vector<int> vecTmp2 = vecSourse;
    for (vector<int>::iterator itr = vecData.begin(); itr != vecData.end(); ++itr)
    {
        for (vector<int>::iterator itrSourse = vecTmp1.begin(); itrSourse != vecTmp1.end(); ++itrSourse)
        {
            if(*itr == *itrSourse)
            {
                vecTmp1.erase(itrSourse);
                break;
            }
        }
    }
 
    for (vector<int>::iterator itr = vecTmp2.begin(); itr != vecTmp2.end(); ++itr)
    {
        if(vecTmp1.end() == std::find(vecTmp1.begin(), vecTmp1.end(), *itr))
            vecTmp2.erase(itr);
    }
    vecData = vecTmp2;
}

我感觉同事的复杂度是:n*log(m) + m*log(m – n)

不知道我算的复杂度对不对…貌似差异不大?