查看数组是否有两个公共元素的最快方法是什么？

Question

假设我们有一个很长的数组，比如说 int 来简化问题。

最快的方法是什么（或者只是 a 最快的方法，如果不是 the 最快的方法），在 C++ 中查看是否有数组在 C++ 中有多个共同元素？

澄清一下，这个函数应该return这个：

[2, 5, 4, 3] => false
[2, 8, 2, 5, 7, 3, 4] => true
[8, 8, 5] => true
[1, 2, 3, 4, 1, 7, 1, 1, 7, 1, 2, 2, 3, 4] => true
[8, '8', 3] => false
[9, 1, 12] => false

一种策略是遍历数组并针对每个数组元素再次遍历数组以进行检查。然而，这可能会非常昂贵和昂贵（字面意思是 O(n^2)）。有没有更好的方法？

Answer 1

(^✠下面更新)将数组元素插入到std::unordered_set and if the insertion fails，这意味着你有重复项。

类似如下：

#include <iostream>
#include <vector>
#include <unordered_set>

bool has_duplicates(const std::vector<int>& vec)
{
    std::unordered_set<int> set;
    for (int ele : vec)
        if (const auto [iter, inserted] = set.emplace(ele); !inserted)
            return true; // has duplicates!
    return false;
}

int main()
{
    std::vector<int> vec1{ 1, 2, 3 };
    std::cout << std::boolalpha << has_duplicates(vec1) << '\n'; // false

    std::vector<int> vec2{ 12, 3, 2, 3 };
    std::cout << std::boolalpha << has_duplicates(vec2) << '\n'; // true
}

^✠更新：正如评论中所讨论的，这可能是也可能不是最快的解决方案。在 OP 的情况下，如的回答中所述，O(N·log(N)) 方法会更好，我们可以通过排序数组检查是否存在重复项来实现。

这里是quick benchmark that I made for the two cases "UnorderedSetInsertion" and the "ArraySort"。以下是 GCC 10.3、C++20、O3 的结果：

Answer 2

合并数据（或创建直方图）如何，并检查结果数据的模式。众数 > 1 表示重复值。

Answer 3

这几乎只是一个排序问题，只是您可以在遇到一个相等且 return 为真时中止排序。

因此，如果您的内存有限（通常是这种情况，实际上并没有时间限制），可以使用在遇到相同元素时中止的就地排序算法；因此，std::sort 带有一个比较器函数，当它遇到相等时会引发异常。复杂度为 O(N·log(N))，但让我们在这里坦诚相待：事实是可能内存寻址的间接性低于树状桶结构的创建可能有帮助。从这个意义上说，我只能建议您实际将其与 JeJos 解决方案进行比较——看起来也很合理！

这里的问题是，很可能没有放之四海而皆准的解决方案：最快的解决方案取决于我们所讨论的整数数量。如果二次复杂度可以保持良好和线性的内存访问，那么即使是二次复杂度也可能比我们的任何“聪明”答案都要好——我几乎可以肯定你在这里的速度不受你的 CPU 的限制，而是受你需要的数据量的限制来回随机播放 RAM。

查看数组是否有两个公共元素的最快方法是什么？

What is the fastest way to see if an array has two common elements?

c++

arrays

algorithm

duplicates

c++17