复制在std向量中只出现一次的元素的最有效方法是什么？

Question

我有一个std向量与这样的元素:

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

找到并复制在此向量中仅出现一次的元素的最有效方法是什么,不包括强力O(n ^ 2)算法？在这种情况下,新列表应包含[188, 220]

Answer 1

1. 做一个 unordered_map<DataType, Count> count;
2. 迭代输入向量,增加每个值的计数.有点count[value]++;
3. 迭代count地图复制键,其值为1.

是的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几乎是一个很好的方式...除了它不允许你迭代键.它有一种检查密钥计数的方法,但是你需要另一套只用于探测密钥的方法.我不认为这是一种更简单的方式.在现代的c ++中,auto计数很容易.我也期待通过algorithm图书馆,但我还没有发现任何transfrom,copy_if,generate等这可能有条件地将元件(映射条目- >值,如果计数为1).

Answer 2

普遍优化的算法非常少.哪种算法效果最好通常取决于正在处理的数据的属性.删除重复项就是一个这样的例子.

是v小而充满大多具有独特的价值？

auto lo = v.begin(), hi = v.end();
std::sort(lo, hi);
while (lo != v.end()) {
    hi = std::mismatch(lo + 1, v.end(), lo).first;
    lo = (std::distance(lo, hi) == 1) ? hi : v.erase(lo, hi);
}

是v小而有重复填充大多？

auto lo = v.begin(), hi = v.end();
std::sort(lo, hi);
while (lo != v.end()) {
    hi = std::upper_bound(lo + 1, v.end(), *lo);
    lo = (std::distance(lo, hi) == 1) ? hi : v.erase(lo, hi);
}

是v 巨大的？

std::unordered_map<int, bool> keyUniqueness{};
keyUniqueness.reserve(v.size());
for (int key : v) {
    bool wasMissing = keyUniqueness.find(key) == keyUniqueness.end();
    keyUniqueness[key] = wasMissing;
}
v.clear();
for (const auto& element : keyUniqueness) {
    if (element.second) { v.push_back(element.first); }
}

等等.