什么是复制在std向量中只发生一次的元素的最有效的方法是什么？ [英] What is the most efficient way of copying elements that occur only once in a std vector?

问题描述

我有一个std向量，有如下的元素：

  [0，1，2，0，2，1， 0，0，188，220，0，1，2] 
  

发现和复制在这个向量中只发生一次的元素，不包括蛮力O（n ^ 2）算法？在这种情况下，新列表应包含 [188，220]

解决方案

1. 创建 unordered_map< DataType，Count> count;


2. 迭代每个值的输入向量增加计数。 计数[值] ++;


3. 迭代计数
   $ b O（n） 。你有哈希，所以对于小数据集法线贴图可能会更有效，但在技术上，它将是 O（n log n）。
   
   
   

   这是离散数据集的好方法。

   
   
   

   代码示例：

     #include< iostream> 
    #include< unordered_map> 
    #include< vector> 
    #include< algorithm> 
    using namespace std; 
    
    int main（）{
    vector< int> v {1,1,2,3,3,4}; 
    unordered_map< int，int>计数; 
    for（const auto& e：v）count [e] ++; 
    vector< int>一旦; 
    for（const auto& e：count）if（e.second == 1）once.push_back（e.first）; 
    for（const auto& e：once）cout<< e  - < '\\\
   '; 
    return 0; 
   } 
     

   我尝试过几个想法。但我没有看到一个方法 map 。 unordered_multiset 几乎是一个伟大的方式...除了它不允许你迭代键。它有一个方法来检查密钥的计数，但你需要另一个集只是为键探测。我不认为它是一个更简单的方式。在现代c ++中， auto 的计数很容易。我还查看了算法库，但我还没有找到任何 transfrom ，可以有条件地变换一个元素（映射条目 - > value，如果count为1）。

   $ b（）可以使用copy_if ， $ b

   I have a std vector with elements like this:

   [0 , 1 , 2 , 0 , 2 , 1 , 0 , 0 , 188 , 220 , 0 , 1 , 2 ]
   

   What is the most efficient way to find and copy the elements that occur only once in this vector, excluding the brute force O(n^2) algorithm? In this case the new list should contain [188, 220]

   解决方案

   1. Make an unordered_map<DataType, Count> count;
   2. Iterate over the input vector increasing count of each value. Sort of count[value]++;
   3. Iterate over the count map copying keys for which value is 1.

   It's O(n). You have hashes so for small data sets normal map might be more efficient, but technically it would be O(n log n).

   It's a good method for discrete data sets.

   Code example:

   #include <iostream>
   #include <unordered_map>
   #include <vector>
   #include <algorithm>
   using namespace std;
   
   int main() {
       vector<int> v{1,1,2,3,3,4};
       unordered_map<int,int> count;
       for (const auto& e : v) count[e]++;
       vector<int> once;
       for (const auto& e : count) if(e.second == 1) once.push_back(e.first);
       for (const auto& e : once) cout << e << '\n';
       return 0;
   }
   

   I have tried few ideas. But I don't see a way around map. unordered_multiset is almost a great way... except it does not allow you to iterate over keys. It has a method to check for count of key, but you would need another set just for keys to probe. I don't see it as a simpler way. In modern c++ with autos counting is easy. I've also looked through algorithm library, but I haven't found any transfrom, copy_if, generate, etc. which could conditionally transform an element (map entry -> value if count is 1).

   这篇关于什么是复制在std向量中只发生一次的元素的最有效的方法是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！