3

Let's say I have two lists, l1 and l2. I want to perform l1 - l2, which returns l1 with any elements that are also elements of l2 removed.

I can think of a naive loop approach to doing this, but that is going to be really inefficient. What is an efficient way of doing this in c++?

As an example, if I have l1 = [1,2,6,8] and l2 = [2,8], l1 - l2 should return [1,6]

thanks you guys

4

4 回答 4

4

顺序重要吗？列表是否包含重复项？

如果不是，我建议做一个set_difference

不过请注意，如果您确实有重复项，我认为 set_difference 只会删除您要删除的重复元素的第一次出现。

于 2012-05-29T20:40:18.087 回答
3

您可以使用散列集在摊销线性时间内执行此操作。

首先，创建一个空集 H。在 L1 上循环并将每个元素插入 H。

然后，循环 L2。对于 L2 的每个元素，当且仅当该元素不在 H 中时，附加到向量。

如果 H 提供恒定时间插入和访问，并且您使用恒定时间附加结构来存储临时结果，则整体算法在列表大小的总和中是线性的。

于 2012-05-29T20:37:46.223 回答
1

天真的方法是O(n^2)，因为您必须将第一个列表中的每个元素与第二个列表中的每个元素进行比较。

稍微好一点的方法是对列表进行排序 ( O(n*log(n)))，然后遍历它们。如果它们是排序的，你只需要一次通过，所以时间是O(n*log(n))。

更好的方法是将第二个列表的所有元素插入std::unordered_set( O(n)) 中，遍历第一个列表 ( O(n)) 的每个元素并检查它是否包含在集合中（O(1)摊销时间）。这应该这样做。- 这仅在您没有重复项时有效。

于 2012-05-29T20:41:37.610 回答
0

如果您想对未排序的情况采用 O(n^2) 天真的方式，您可以使用一点<algorithm>和std::bind（或者如果这不是一个选项，则提升）技巧来做到这一点：

#include <list>
#include <algorithm>
#include <iostream>
#include <functional>
#include <iterator>

int main() {
  std::list<std::string> a = {"foo", "bar", "baz", "woof"},
                         b = {"baz", "bar", "random other thing"};

  a.erase(std::remove_if(a.begin(), a.end(), std::bind(std::equal_to<std::list<std::string>::iterator>(), b.end(), std::bind(std::find<std::list<std::string>::iterator, std::string>, b.begin(), b.end(), std::placeholders::_1))), a.end());

  std::copy(a.begin(), a.end(), std::ostream_iterator<std::string>(std::cout, "\n"));
}
于 2012-05-29T21:21:21.340 回答