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

Question

假设我有一个包含以下元素的 vector {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> 样式的模板，并使用 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, ", "));
}

这可以输出到任何类型的迭代器。 There are special iterators you can use that when written to will insert the value into a container.