manière efficace d'obtenir des éléments uniques à partir d'un vecteur de paires

Question

j'ai un vecteur de paires d'entiers qui ressemble en quelque sorte comme ça:

(0, 1) 
(1, 9) 
(2, 3) 
(6, 1) 
(4, 0) 

Je veux extraire des éléments uniques à partir de là, de sorte que le résultat semble que suit:
‍‍0‍, 1, 9, 2, 3, 6, 4 (fondamentalement juste tous les nombres sans doublons)

En ce moment je fais comme ça:

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

Existe-t-il un moyen plus efficace de le faire?

Answer 1

Votre solution actuelle est O(n^2). Vous pouvez réduire le balayage linéaire pour les éléments déjà vus à O(1) amorti en utilisant std::unordered_set pour stocker les numéros déjà vus; Cela va améliorer votre temps d'exécution à O(n).

Voici un algorithme amélioré:

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

Voir un exemple Live On Coliru

Answer 2

Existe-t-il un moyen plus efficace de le faire?

Oui, il y a. std::find a une complexité O (n) pour le vecteur, donc le répéter pour chaque élément vous donne la complexité O (n * n).

Une alternative simple est d'ajouter chaque élément dans std::set. La complexité de construction de l'ensemble est O (n log n).

Answer 3

ne se mesure pas, mais je pense qu'il est plus rapide ...

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