如何在向量中查找第一个重复项 - C++？

我有不同值的向量和它们中的一些可能出现两次。（只有两次）
如何找到第一个重复项目？如何在向量中查找第一个重复项 - C++？

赞：[a] [b] [b] [a]
然后，我需要'b'。

（很抱歉的新手问题。）

2011-04-08 Shiki

如果你知道元素的值，可以说，它的字母表，你可以有一个载体 VEC（26）;并为每个值做vec [c -'a'] ++;如果它不为零，那么该值已出现两次。它更快，然后使用std :: set。但是，你确定了这些值是什么。 – hidayat 2011-04-08 11:35:49

谢谢你们提供非常快速和有用的答案。 :) – Shiki 2011-04-08 15:12:34

如果您正在寻找邻近的重复，你可以简单地使用std::adjacent_find。

~~如果重复不一定是相邻的，那么你可以先std::sort向量，然后对结果使用std::adjacent_find。~~（见下面@ AIX的评论）

或者，你可以每个元素推入一个std::set，寻找碰撞为你这样做。

2011-04-08 11:30:23

（+1）排序方法不一定会根据问题的要求定位* first *重复。 – NPE 2011-04-08 11:32:28

@aix：非常好的一点。 – 2011-04-08 11:33:36

有很多回答这个问题。要找到最好的之一，有必要了解您的使用场景的上下文。比如说，好吗首先有重复吗？你将如何处理重复搜索的结果？我们可以随时使用并行结构来处理矢量吗？和更多...

所以，很多方法之一是将它们迭代到std::set<>。看看返回std::pair<>的second参数来获取设定与否是否存在的价值，那么你会得到的第一个副本，并能摆脱困境set -adding的。

2011-04-08 11:34:43

如果你不想使用额外的存储空间，大致有两种解决方案。第一个是蛮力：对于每个元素i，检查它是否等于元素0..i-1。这是O(N*N)（最明显的情况是：最后两个元素是第一个重复项）。

第二个解决方案是使搜索更快，通过保持范围0..i。排序。在排序过程中，您可以轻松地找到重复项目。冒泡排序是有效的，因为范围0..i-1已经在前一次迭代中排序。仍然O(N*N)最坏的情况，但O(N)如果范围发生之前排序。

2011-04-08 14:17:48 MSalters

回答