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

Question

我一直在尝试想出一种方法来编写一种有效的算法来对两个 vector/数组执行未排序的交集，但没有成功。我正在使用一个大型非唯一数组(通常为 500,000 到 1,000,000 个值)和一个相对较小(最多可能有 5000 个值)的唯一数组。

我已经看到这里建议的各种方法涉及 unordered_sets 等技术，但据我了解，如果其中一个数组不唯一，这将不起作用。其次，我不想让输出 vector 包含两个数组共有的数字，而是让输出 vector 包含这些公共(public)值相对于较大数组的索引。因此，如果较大的数组有 5 个位置等于较小数组中的值之一，我需要这 5 个索引中的每一个。也许类似于 python 的 in1d 函数。

有人有什么想法吗？谢谢

Answer 1

将唯一边放入一个unordered_set中，将非唯一边一个一个遍历。如果您在 unordered_set(unique_side) 中找到位于 non_unique_side[i] 的项目，请将 i 添加到结果中。

假设 unordered_set 被实现为具有 O(1) 分摊插入和查找时间的哈希集，此算​​法使您得到 O(L+S) 时间复杂度，其中 L 是较大列表中的项数，S 是较小集合中的项数。这是您通过十字路口的最快速度。