Je dois trouver 4 les plus grands nombres dans un vecteur const et retourner leurs positions. Je veux que ce code ait la meilleure complexité temporelle et spatiale. Ma première idée est de copier ce vecteur const dans le vecteur et de le trier par bulles 4 fois. Cela me donne 4 * N mais je dois créer un vecteur. La deuxième idée est de tout mettre de ce vecteur const dans priority_queue. Cela me donne une complexité temporelle N * log2 (N) sans créer d'autres variables. Le maximum de N est d'environ 100.

Existe-t-il d'autres options pour le faire de la manière la plus rapide et la moins encombrante?

EDIT: Peu importe lequel est le plus gros, j'ai juste besoin de renvoyer la position de ces 4 éléments dans le vecteur d'entrée.

2
Asachi 7 mai 2020 à 18:55

4 réponses

Meilleure réponse

Vous pouvez l'implémenter assez facilement avec un vector supplémentaire et l'algorithme nth_element, qui est de O(n) temps:

std::vector<int> const v = ...;

// create a vector of elements with original indexes
std::vector<std::pair<int,int>> res;

// populate the result vector
int k = 0;
for (int i : v)
  res.push_back({i,k++});

// find the maximum 4 elements
std::nth_element(res.begin(), res.begin() + 4, res.end(),
   [](auto const &a, auto const &b) { return a.first > b.first; });

Voici une démo.

1
cigien 7 mai 2020 à 16:53

Lire les 4 premiers éléments dans un vecteur de 4. trier ce vecteur de sorte que le minimum des 4 soit dans l'indice 0.

Boucle sur les éléments restants du vecteur const, si la valeur actuelle> min, remplacez-la et triez à nouveau le vecteur à 4 éléments

0
nivpeled 7 mai 2020 à 16:01

Oui, utilisez un tas de taille quatre. Ensuite, vous parcourez le vecteur et mettez à jour le tas en conséquence.

Exemple de code utilisant des méthodes de tas std et recherchant des valeurs minimales (à partir d'ici) suit.

const std::vector<int> input;
const size_t n = 4;
std::vector<int> ret(n);
auto dfirst = ret.begin(), dlast = ret.end();

// initialize heap with infinity distances
std::fill(dfirst, dlast, 100000000000); // do better here

for (auto it = input.begin(); it != input.end(); ++it)
{
    if (*it < *dfirst) {
        // remove max. value in heap
        std::pop_heap(dfirst, dlast); // add comparator as third arg

        // max element is now on position "back" and should be popped
        // instead we overwrite it directly with the new element
        *(dlast-1) = *it;
        std::push_heap(dfirst, dlast); // add comparator as third arg
    }
}
std::sort_heap(dfirst, dlast); // add comparator as third arg
return ret;

Adaptez-vous en conséquence:

  • Utilisez une paire d'index, valeur dans le tas pour garder une trace des positions que vous souhaitez retourner
  • Utilisez un comparateur qui compare la valeur de la paire et établit une desc. commande

C'est plus générique que la solution de @Jugal Rawlani si votre nombre n peut changer / augmenter dans le futur. Sinon, son idée l'emporte.

1
ypnos 7 mai 2020 à 16:16

Solution O (n)

std::vector<int>::iterator max1 = v.begin(), max2 = v.begin(), max3 = v.begin(), max4 = v.begin();
for(std::vector<int>::iterator it = v.begin(); it != v.end(); it++) {
    if((*max1) < (*it)) {
        max4 = max3;
        max3 = max2;
        max2 = max1;
        max1 = it;
    } else if((*max2) < (*it)) {
        max4 = max3;
        max3 = max2;
        max2 = it;
    } else if((*max3) < (*it)) {
        max4 = max3;
        max3 = it;
    } else if((*max4) < (*it)) {
        max4 = it;
    }
}    
3
Jugal Rawlani 7 mai 2020 à 16:25