从对矢量中获取唯一元素的有效方法

Question

我有一对整数对的向量,看起来像这样:

(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;
}

有没有更有效的方法呢？

Answer 1

您当前的解决方案是O(n^2).您可以通过使用存储已经看到的数字来将已经看到的元素的线性扫描减少到摊销; 这将改善您的运行时间.O(1)std::unordered_setO(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示例