c++ - 从另一组整数中高效移除一组整数

Question

我有一组(大)整数 S，我想运行以下伪代码:

set result = {};
while(S isn't empty)
{
  int i = S.getArbitraryElement();
  result.insert(i);
  set T = elementsToDelete(i);
  S = S \ T; // set difference
}

函数 elementsToDelete 是高效的(在 S 的初始大小上是次线性的)并且 T 的大小很小(假设它是常量) . T 可能包含不再在 S 中的整数。

有没有比 O(|S|^2) 更快的实现上述方法的方法？我怀疑我应该能够得到 O(|S| k)，其中 k 是 elementsToDelete 的时间复杂度。我当然可以使用 std::set_difference 以直接的方式实现上述内容，但我的理解是 set_difference 是 O(|S|)。

Answer 1

使用 std::set S;，您可以:

for (auto k : elementsToDelete(i)) {
    S.erase(k);
}

当然 erase 的查找是 O(log(S.size()))，而不是 O(1) 你要求。这可以通过 std::unordered_set 来实现，假设没有太多的碰撞(这通常是一个很大的假设，但在特定情况下通常是正确的)。

尽管名称如此，std::set_difference 算法与std::set 并没有太多关系。它适用于任何你可以按顺序迭代的东西。无论如何，它不是用于容器的就地修改。由于 T.size() 在这种情况下很小，您真的不希望每次删除一批元素时都创建一个新容器。在结果集足够小的另一个示例中，它会比重复 erase 更有效。