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

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

Is there any more efficient way to do it?

是的，有。 std::find 向量的复杂度为 O(n)，因此对每个元素重复它会给你 O(n*n) 的复杂度。

一个简单的替代方法是将每个元素添加到 std::set 中。构建集合的复杂度为 O(n log n).

Answer 2

您当前的解决方案是O(n^2)。您可以通过使用 std::unordered_set 存储已经看到的数字，将已经看到的元素的 linear-scan 减少到摊销的 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

Answer 3

没测过，不过我觉得比较快...

#include <iostream>
#include <algorithm>
#include <vector>

std::vector<int> getElements(std::vector<std::pair<int, int>>& S) {
    std::vector<int> V;
    V.reserve(2*S.size());
    for (const auto& i : S) {
        V.push_back(i.first);
        V.push_back(i.second);
    }
    std::sort(V.begin(), V.end());
    V.erase(std::unique(V.begin(), V.end()), V.end()); 
    return V;
}

int main() 
{
    std::vector<std::pair<int, int>> v{{0, 1},{1, 9},{2, 3},{6, 1},{4, 0}};

    for(const auto& i : getElements(v))
        std::cout << i << ' ';
    std::cout << '\n';
}

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

Efficient way to get unique elements from a vector of pairs

c++

vector

std