c++ - 嵌套循环导致复杂性效率降低？

Question

我编写了一个简单的函数，它根据另一个 vector (V1) 的值从一个 vector (V2) 中删除元素:

std::vector<int> V1={6,2,3,4};
std::vector<int> V2={9,4,8,6,7};

for(int i=0; i<V1.size(); i++)
{
   if(!V2.empty())
   {
     V2.erase(std::remove(V2.begin(),V2.end(),V1[i]),V2.end());
   }
}

我的挑战是上述需要复杂度为 O(n)。目前这是 O(n*m)，n 是 V1，m 是 V2。

注意数组不能也不能排序，因为元素的原始索引值是必需的。

问题:

1. 我说“V2.erase”阻止此函数变为 O(n) 是否正确？ (因为它是 for 循环中的嵌套迭代)。

2. 有没有办法通过在循环外执行删除操作来解决这个问题？

Answer 1

为什么不使用 std::set_difference :

std::vector<int> test(
    std::vector<int> v1,
    std::vector<int>& v2)
{
    // The algorithm we use requires the ranges to be sorted:
    std::sort (v1.begin(), v1.end());
    std::sort (v2.begin(), v2.end());

    // our output vector: reserve space to avoid copying:
    std::vector<int> v3;
    v3.reserve (v2.size());

    // Use std::set_difference to copy the elements from
    // v2 that are not in v1 into v3:
    std::set_difference (
        v2.begin(), v2.end(),
        v1.begin(), v1.end(),
        std::back_inserter(v3));

    return v3;
}

如果 v1.size() == n 和 v2.size() == m 运行时间大致为:

---

好的，那么这个怎么样:

void test2(
    std::vector<int> v1,
    std::vector<int> v2)
{
    // We can still sort this without affecting the indices
    // in v2:
    std::sort (v1.begin(), v1.end());

    // Replace all the elements in v1 which appear in v2
    // with -1:
    std::replace_if (v2.begin(), v2.end(),
        [&v1] (int v)
        {
            return std::binary_search(v1.begin(), v1.end(), v);
        }, -1);
}

非线性；估计复杂性留给 OP 练习。

---

第三种选择是这样的:

void test3(
    std::vector<int> v1,
    std::vector<int>& v2)
{
    // We can still sort this without affecting the indices
    // in v2:
    std::sort (v1.begin(), v1.end());

    auto ret = std::stable_partition (
        v2.begin(), v2.end(),
        [&v1] (int v)
        {
            return !std::binary_search(v1.begin(), v1.end(), v);
        });

    v2.erase (ret, v2.end());
}

同样，不是线性的，而是选项...