如何在向量中查找第一個重複項 - 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

回答