我有一个整数对 vector ,看起来有点像这样:
(0, 1)
(1, 9)
(2, 3)
(6, 1)
(4, 0)
我想从那里提取独特的元素,以便结果如下所示:
0, 1, 9, 2, 3, 6, 4
(基本上只是所有没有重复的数字)
目前我是这样做的:
std::vector<int> getElements(std::vector<std::pair<int, int>> S) {
std::vector<int> V;
for (std::vector<std::pair<int, int>>::iterator i = S.begin(); i != S.end(); i++) {
if (std::find(V.begin(), V.end(), i->first) == V.end()) {
V.push_back(i->first);
}
if (std::find(V.begin(), V.end(), i->second) == V.end()) {
V.push_back(i->second);
}
}
return V;
}
有没有更有效的方法呢?
最佳答案
您当前的解决方案是 O(n^2)
。您可以通过使用 std::unordered_set
存储已看到的元素,将已看到元素的线性扫描 减少到分摊的 O(1)
数字;这会将您的运行时间提高到 O(n)
。
这是一个改进的算法:
std::vector<int> getElements(std::vector<std::pair<int, int>> S) {
std::unordered_set<int> ss;
std::for_each(S.begin(), S.end(), [&ss](const auto& p) {
ss.insert(p.first);
ss.insert(p.second);
});
return std::vector<int>(ss.begin(), ss.end());
}
查看示例 Live On Coliru
关于c++ - 从成对 vector 中获取唯一元素的有效方法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/41884512/