非唯一的C++未排序交集算法

Question

我一直在试图想出一种高效的算法来执行两个向量/数组的未排序交集，但是没有成功。我正在使用一个大的非唯一数组（通常有500,000到1,000,000个值）和一个相对较小的（最多可能有5000个值）唯一数组。

我看到这里提出了各种方法，包括使用unordered_sets等技术，但据我所知，如果其中一个数组是非唯一的，则无法正常工作。其次，我希望输出向量包含相对于较大数组的那些共同值的索引，而不是包含两个数组共同元素的输出向量。因此，如果较大的数组有5个位置等于较小的数组中的一个值，我需要这5个索引。也许类似于Python的in1d函数的东西。

有任何想法吗？谢谢

- zach

---

关于非唯一的一侧，您能否澄清一下{1,2,2,3}和{2,3}的交集是什么？ - Sergey Kalinichenko

当然。{1,2,3}将是{1,2,2,3}中被{2,3}交集的元素的索引。 - zach

你的值是什么？它们能被有效地哈希吗？ - Andriy Tylychko

这两个数组的值只是任意整数。 - zach

Answer 1

将唯一的一边放入一个 unordered_set 中，然后逐个检查非唯一的一边。如果你在 unordered_set(unique_side) 中找到了一个 non_unique_side[i] 的项目，则将 i 添加到结果中。

假设 unordered_set 是实现为一个哈希集合，具有 O(1) 平均插入和查找时间，那么这个算法可以获得 O(L+S) 的时间复杂度，其中 L 是较大列表中的项目数，S 是较小集合中的项目数。这是您可以执行的最快的交集。

- Sergey Kalinichenko

---

好的，这听起来就是我想要的。谢谢。 - zach

Answer 2

创建另一个向量，其中包含大数组中的所有索引。然后使用一个级别的间接性来排序索引，并对唯一数组执行相同操作或在原地进行排序。然后使用允许一个级别的间接性并将映射向量中的索引放入最终结果的比较进行正常有序交集。

- Mark B

Answer 3

你可以将大数组从其值映射到int。

例如：unordered_map<int,int> 当你映射较大的数组时，只需增加找到的每个项的值即可。

然后，您只需要遍历较小的值，并对于每个值检查它是否存在于映射中。如果存在，则将映射的int中的项目数添加到结果向量中。

所以，如果你有5个六，map [6] = 5..所以只需将5个6的实例添加到结果值中。

编辑：

如果您想要索引，可以将其映射到int的向量，并保留每个值找到的索引向量。

- Yochai Timmer

---

从对我的评论的回应来看，似乎OP正在寻找非唯一侧项目的索引，而不是它们本身的值。 - Sergey Kalinichenko

没问题，你可以映射到索引向量。 - Yochai Timmer