c++ - 复制标准 vector 中仅出现一次的元素的最有效方法是什么？

我有一个像这样的std vector :

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

除了蛮力O(n ^ 2)算法之外，查找和复制在此 vector 中仅出现一次的元素的最有效方法是什么？在这种情况下，新列表应包含[188, 220]

最佳答案

制作一个unordered_map<DataType, Count> count;

遍历输入 vector ，增加每个值的计数。某种count[value]++;

遍历值是1的count映射复制键。

这是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> 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;
}

我尝试了一些想法。但是我没有办法解决map。 unordered_multiset几乎是一种很棒的方法...除了它不允许您迭代键外。它有一种检查 key 计数的方法，但是您需要另一组 key 来进行探测。我不认为这是一种更简单的方法。在带有auto的现代c++中，计数很容易。我还浏览了algorithm库，但没有找到可以有条件地转换元素的任何transfrom，copy_if，generate等(映射计数->如果count为1的值)。

关于c++ - 复制标准 vector 中仅出现一次的元素的最有效方法是什么？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/35215773/