有效的方式，從對

我有對的整數的向量的向量得到獨特的元素，看起來莫名其妙地像：有效的方式，從對

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

有沒有更有效的方法來做到這一點？

來源

2017-01-26 vgeclair

使用'set'或'地圖'。 –

你關心訂單嗎？ – clcto

@clcto否，順序無關 – vgeclair

您目前的解決方案是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

來源

2017-01-26 23:08:21 WhiZTiM

謝謝！只是試了一下，完美的作品:) – vgeclair

@vgeclair，歡迎您..隨時。 – WhiZTiM

有沒有更有效的方法來做到這一點？

是的，有。 std::find對於向量具有O（n）複雜性，因此對每個元素重複它會給出O（n * n）複雜度。

一個簡單的選擇是將每個元素添加到std::set。構建集合的複雜性是O（n log n）。

來源

2017-01-26 23:07:53 user2079303

謝謝，我可以想到套:) – vgeclair

未測，但我認爲這是更快...

#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'; 
}

來源

2017-01-26 23:25:12 Loreto

有效的方式，從對

回答

相關問題