0

如何有效地比较 C++ 中的两个向量，其内容无法进行有意义的排序？

我读了很多帖子，但大多数都在谈论首先对两个向量进行排序，然后比较元素。但就我而言，我无法以有意义的方式对向量进行排序以帮助进行比较。这意味着我将不得不进行 O(N^2) 操作而不是 O(N)，我将不得不比较第一个向量中的每个元素，并尝试在第二个向量中找到它的唯一匹配项。所以我必须匹配所有元素，如果我能找到每个元素的唯一匹配，那么向量是相等的。

有没有一种有效而简单的方法来做到这一点？我必须自己编码吗？

编辑：通过有意义的排序，我的意思是一种对它们进行排序的方法，以便以后您可以以线性方式比较它们。

谢谢

4

4 回答 4

9

如果可以以某种有意义的方式对元素进行散列O(n)，则可以通过使用散列图获得预期的性能：将列表 A 中的所有元素插入散列图中，并且对于列表 B 中的每个元素，检查它是否存在于散列图中。

在 C++ 中，我相信这unordered_map是标准的 hashmap 实现（尽管我自己没有使用过）。

于 2013-06-06T12:40:58.037 回答
5
  1. 将vector的所有元素A放入一个哈希表中，其中元素是键，值是你添加元素的次数的计数器。[预计 O(n)]
  2. 遍历向量B并减少哈希表中每个元素的计数器。[预计 O(n)]
  3. 遍历哈希表并检查每个计数器是否为 0。 [O(n) 预期]

= O(n) 预期运行时间。

于 2013-06-06T12:41:21.587 回答
1

没有理由使用地图，因为没有要关联的值，只有键（元素本身）。在这种情况下，您应该考虑使用 aset或unordered_set. 将 A 中的所有元素放入一个新集合中，然后遍历 B。对于每个元素，if( set.find(element) == set.end() ) return false;

如果您要根据某个任意值对数组进行排序，您可能需要查看 C++11's hash，它返回一个 size_t。使用它，您可以编写一个比较器，它对两个对象进行散列并比较它们，您可以将其与 std::sort 一起使用以对其执行 O(n log n) 排序。

于 2013-06-06T17:04:32.693 回答
0

如果你真的不能对向量进行排序，你可以试试这个。C++ 大师请自由指出缺陷、利用 STL 和其他库的明显失败、无法理解以前的答案等 :) 如有必要，请提前道歉。

有一个整数向量，0..n，称为 C。这些整数是向量 B 中每个元素的索引。对于向量 A 中的每个元素，根据 C 中的 B 索引将其与 B 中的元素进行比较。如果你找到匹配项从 C 中删除该索引。C 现在短了一个。对于下一个 A，您将再次根据 C 中的索引搜索 B，该索引较短，花费的时间更少。如果你幸运的话，它会很快。

或者，您可以建立一个已经检查过的 B 索引向量，以便在下次循环时忽略那些 B。节省先构建一个完整的 C。

于 2013-06-06T17:28:16.040 回答