groupe dupliquer les objets dans vector - C++

Question

INPUT : [3,3,3,2,2,2,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0]

OUTPUT : [[3,3,3],[2,2,2],[1,1,1,1,1],[0,0,0,0,0,0,0,0,0,0]]

l'entrée est un vecteur d'entiers tandis que la sortie est un vecteur de vecteurs de ints. Le but est de le faire de la manière la plus efficace possible en termes de temps.

La solution que je suis actuellement en utilisant est la suivante:

vector<vector<int> results; 
vector<int> result; 

for(int i = 0 ; i < list.size() - 1 ; i++){ 
    result.push_back(list[i]); 
    if (list[i] != list[i+1]){ 
     results.push_back(result); 
     result.clear(); 
    } 
} 

result.push_back(list[list.size()-1]); 
results.push_back(result); 

• crédit: @kabanus

Answer 1

Vous êtes proche. Vous avez déjà deviné votre problème des limites, mais considérez ce qui se passe à l'interface des clusters:

..2,2,3,3... 
    ^^ 
    i i+1 

Vous allez entrer dans le else (else if est inutile si la condition est l'exact opposé de l'if d'origine) et oublier pour ajouter ce dernier 2. S'il n'y a pas de doublons dans le vecteur, comme

`{1,2,3,4}` 

Vous n'êtes pas allez ajouter quelque chose, mais les clusters vides! Donc, vous voulez toujours ajouter le numéro, plutôt que vous êtes dans un cluster ou le terminer. Si vous terminez un cluster, vous devez également ajouter et effacer.

for(int i = 0 ; i < sorted.size()-1 ; i++){ 
    cluster.push_back(sorted[i]); 
    if (sorted[i] != sorted[i+1]){ 
     clusters.push_back(cluster); 
     cluster.clear(); 
    } 
} 

Enfin, comme @ tobi303 mentionné le dernier élément est manquant. Ceci est particulièrement évident avec une liste avec un seul élément ({3}). Notez que le dernier cluster n'est pas ajouté dans tous les cas, que ce soit un nouvel élément unique à la fin ou juste un cluster final. Donc, une fois que nous quittons le for, nous avons besoin d'encore une vérification (pas vraiment) - si le cluster est vide, cela signifie que le dernier élément n'en fait pas partie et qu'il est nouveau. Sinon, le dernier cluster n'a pas encore été ajouté et vous devez y ajouter le dernier élément, puis ajouter le cluster. Je vous laisse celui-ci.

Answer 2

Vous devez utiliser le standard algorithm library autant que possible

Ceci est une mise en œuvre possible:

template <class T> 
auto make_clusters(std::vector<T>& v) -> std::vector<std::vector<T>> 
{ 
    std::vector<std::vector<T>> clusters; 

    auto cluster_begin = v.begin(); 
    while (cluster_begin != v.end()) 
    { 
     auto elem = *cluster_begin; 

     auto cluster_end = std::find_if(cluster_begin, v.end(), 
             [&](int e) { return e != elem; }); 
     clusters.emplace_back(std::distance(cluster_begin, cluster_end), elem); 

     cluster_begin = cluster_end; 
    } 

    return clusters; 
}