Quelle est la manière la plus efficace de copier des éléments qui ne se produisent qu'une seule fois dans un vecteur std?

j'ai un vecteur std avec des éléments comme ceci:

[0 , 1 , 2 , 0 , 2 , 1 , 0 , 0 , 188 , 220 , 0 , 1 , 2 ]

Quel est le moyen le plus efficace pour trouver et copier les éléments qui ne se produisent qu'une seule fois dans ce vecteur, en excluant l'algorithme de la force brute O(N^2)? Dans ce cas, la nouvelle liste doit contenir [188, 220]

15
demandé sur MSalters 2016-02-05 06:24:50

4 réponses

  1. unordered_map<DataType, Count> count;
  2. parcourir le vecteur d'entrée augmente comte de chaque valeur. Sorte de count[value]++;
  3. parcourir count carte copier des clés dont la valeur est 1.

O(n). Vous avez des hachures donc pour les petits ensembles de données la carte normale pourrait être plus efficace, mais techniquement il serait O(n log n).

C'est une bonne méthode pour les ensembles de données.

exemple de Code:

#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v{1,1,2,3,3,4};
    unordered_map<int,int> count;
    for (const auto& e : v) count[e]++;
    vector<int> once;
    for (const auto& e : count) if(e.second == 1) once.push_back(e.first);
    for (const auto& e : once) cout << e << '\n';
    return 0;
}

je ont essayé quelques idées. Mais je ne vois pas un moyen de contourner map. unordered_multiset est presque un grand chemin... sauf qu'il ne vous permet pas d'itérer sur les clés. Il a une méthode pour vérifier le nombre de clés, mais vous auriez besoin d'un autre ensemble juste pour les clés à sonder. Je ne vois pas ça comme une façon plus simple. En c++ moderne avec autos de comptage est facile. J'ai aussi regardé par algorithm bibliothèque, mais je n'ai pas trouvé d' transfrom,copy_if,generate, etc. qui pourrait transformer conditionnellement un élément (entrée map - > valeur si le comte est 1).

9
répondu luk32 2016-02-05 10:17:07

il existe très peu d'algorithmes universellement optimaux. L'algorithme qui fonctionne le mieux dépend habituellement des propriétés des données qui sont traitées. La suppression des doublons en est un exemple.

v petites et remplies surtout de valeurs uniques?

auto lo = v.begin(), hi = v.end();
std::sort(lo, hi);
while (lo != v.end()) {
    hi = std::mismatch(lo + 1, v.end(), lo).first;
    lo = (std::distance(lo, hi) == 1) ? hi : v.erase(lo, hi);
}

v petits et remplis surtout de doublons?

auto lo = v.begin(), hi = v.end();
std::sort(lo, hi);
while (lo != v.end()) {
    hi = std::upper_bound(lo + 1, v.end(), *lo);
    lo = (std::distance(lo, hi) == 1) ? hi : v.erase(lo, hi);
}

vgigantesques?

std::unordered_map<int, bool> keyUniqueness{};
keyUniqueness.reserve(v.size());
for (int key : v) {
    bool wasMissing = keyUniqueness.find(key) == keyUniqueness.end();
    keyUniqueness[key] = wasMissing;
}
v.clear();
for (const auto& element : keyUniqueness) {
    if (element.second) { v.push_back(element.first); }
}