仅保留重复的值-Vectors C ++

Question

假设我有一个包含以下元素{1、1、2、3、3、4}的向量，我想编写一个使用c ++代码的程序，以删除唯一值，并且仅将重复项保留一次。因此，最终结果将是这样的{1,3}。

到目前为止，这是我所做的，但是要花很多时间，请问有什么方法可以提高效率，

vector <int> g1 = {1,1,2,3,3,4}
vector <int> g2;

for(int i = 0; i < g1.size(); i++)
{
  if(count(g1.begin(), g1.end(), g1[i]) > 1)
    g2.push_back(g1[i]);

}

v.erase(std::unique(g2.begin(), g2.end()), g2.end());

for(int i = 0; i < g2.size(); i++)
{
  cout << g2[i];
}

Answer 1

我的方法是创建一个<algorithm>-style模板，并使用进行unordered_map计数。这意味着您只需对输入列表进行一次迭代，时间复杂度为O(n)。O(n)但是，它确实使用了额外的内存，并且并非特别适合缓存。这也假定输入中的类型是可哈希的。

#include <algorithm>
#include <iostream>
#include <iterator>
#include <unordered_map>

template <typename InputIt, typename OutputIt>
OutputIt copy_duplicates(
        InputIt  first,
        InputIt  last,
        OutputIt d_first)
{
    std::unordered_map<typename std::iterator_traits<InputIt>::value_type,
                       std::size_t> seen;
    for ( ; first != last; ++first) {
        if ( 2 == ++seen[*first] ) {
            // only output on the second time of seeing a value
            *d_first = *first;
            ++d_first;
        }
    }
    return d_first;
}

int main()
{
    int i[] = {1, 2, 3, 1, 1, 3, 5}; // print 1, 3,
    //                  ^     ^
    copy_duplicates(std::begin(i), std::end(i),
                    std::ostream_iterator<int>(std::cout, ", "));
}

这可以输出到任何类型的迭代器。您可以使用特殊的迭代器，将其写入时会将值插入到容器中。