查看数组是否有两个公共元素的最快方法是什么？
zix*_*uan 8 c++ arrays algorithm duplicates c++17
假设我们有一个很长的数组，int可以让问题变得更简单。
在 C++ 中查看数组是否具有多个 C++ 公共元素的最快方法是什么（或者只是一种快速方法，如果它不是最快的话）？
为了澄清，这个函数应该返回：
[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
[9, 1, 12] => false
一种策略是循环遍历数组，并对每个数组元素再次循环遍历数组进行检查。然而，这可能非常昂贵（字面意思O(n^2)）。还有更好的办法吗？
JeJ*_*eJo 14
（\xe2\x9c\xa0更新如下）将数组元素插入到a中std::unordered_set，如果插入失败，则意味着有重复项。
类似如下：
\n#include <iostream>\n#include <vector>\n#include <unordered_set>\n\nbool has_duplicates(const std::vector<int>& vec)\n{\n std::unordered_set<int> set;\n for (int ele : vec)\n if (const auto [iter, inserted] = set.emplace(ele); !inserted)\n return true; // has duplicates!\n return false;\n}\n\nint main()\n{\n std::vector<int> vec1{ 1, 2, 3 };\n std::cout << std::boolalpha << has_duplicates(vec1) << \'\\n\'; // false\n\n std::vector<int> vec2{ 12, 3, 2, 3 };\n std::cout << std::boolalpha << has_duplicates(vec2) << \'\\n\'; // true\n}\n\n
\xe2\x9c\xa0更新：正如评论中所讨论的，这可能是也可能不是最快的解决方案。在 OP 的情况下，正如Marcus M\xc3\xbcller的答案中所解释的那样，一种O(N\xc2\xb7log(N))方法会更好，我们可以通过对排序数组进行重复检查来实现这一点。
这是我为“ UnorderedSetInsertion ”和“ ArraySort ”这两种情况所做的快速基准测试。以下是GCC 10.3、C++20、O3的结果：
\n
- 请注意，在实际问题中，我并没有赋予朗道符号太多的意义——对于适合 L1/L2 的小向量，进行冒泡排序，当遇到重复项时中止，速度会更快，尽管当然渐近，冒泡排序是灾难性的。你的算法很好并且是线性时间的——直到你的桶变得很大并且你需要为它们获取内存。*我不认为这在实践中的复杂性实际上是线性的*，只是因为核心算法看起来好像是线性的 - 它忽略了内存分配问题，以及您正在执行非常不规则的内存访问模式的事实。 (2认同)
这几乎只是一个排序问题，只是一旦遇到单个相等并返回 true 就可以中止排序。
\n因此，如果您的内存有限（通常是这种情况，实际上不受时间限制），则可以使用在遇到相同元素时中止的就地排序算法；因此，std::sort比较器函数在遇到相等时会引发异常。复杂度为 O(N\xc2\xb7log(N))，但老实说：事实上，与创建树状存储桶结构相比，这在内存寻址中可能不太间接。从这个意义上说，我只能建议您将其与 JeJos 解决方案 \xe2\x80\x93 进行比较，它看起来也相当合理！
这里的问题是，很可能没有一种万能的解决方案：最快的解决方案将取决于我们正在讨论的整数的数量。即使二次复杂度也可能比我们的任何“聪明”答案都要好，如果这能让内存访问保持良好和线性 \xe2\x80\x93 我几乎可以肯定你的速度不受你的 CPU 的限制，而是受你的数据量的限制需要在 RAM 之间进行洗牌。
\n