Trouver le plus grand et le deuxième élément de la plus grande partie de la gamme

suppose que vous voulez dire que vous voulez trouver les deux plus grandes valeurs uniques de la liste.

Si la liste est déjà triée, alors regardez simplement le deuxième dernier élément (ou plutôt, itérer à partir de la fin à la recherche de la deuxième dernière valeur. ).

Si la liste est non achouée, alors ne vous inquiétez pas pour le trier. Le tri est au meilleur O (n lg n). Une itération linéaire simple est O (n), donc simplement une boucle sur les éléments suivant la piste: xxx

Il y a bien sûr d'autres critères, et ceux-ci pourraient tous être mis dans le test à l'intérieur. la boucle. Toutefois, si vous voulez dire que deux éléments qui ont la même valeur la plus importante devraient être trouvés, vous devez envisager de savoir ce qui se passe aurait trois éléments ou plus ont tous la valeur la plus importante, ou si deux ou plusieurs éléments ont la deuxième plus grande.

for (e: all elements) {
 if (e > largest) {
   second = largest;
   largest = e;
 } else if (e > second) {
   second = e;
 }
}
You could either initialize largest and second to an appropriate lower bound, or to the first two items in the list (check which one is bigger, and don't forget to check if the list has at least two items)

Vous pouvez numériser la liste en une seule passe et enregistrer les valeurs 1 er et 2nd, qui comporte une efficacité O (n) pendant le tri (n journal n).

EDIT:
Je pense que ce genre partiel est O (n log K)

La réponse dépend si vous ne voulez que les valeurs, ou aussi des itérateurs pointant sur les valeurs.

Modification mineure de @Will Réponse. P>

v::value_type second_best = 0, best = 0;
for(v::const_iterator i=v.begin(); i!=v.end(); ++i)
{
   if(*i > best)
   {
     second_best = best;
     best = *i;
   }
   else if (*i > second_best)
   {
     second_best = *i;
   }
}

NTH_Element (commencer, commencer + n, fin, comparer) code> place l'élément qui serait NTH (où "premier" est "0ème") si la plage [commence, fini) code> ont été triés à la position commencements + n code> et veille à ce que tout de [commence, commence + n) code> apparaisse avant le nième élément de la liste triée. Donc, le code que vous voulez est:

nth_element(container.begin(),
            container.begin()+1,
            container.end(),
            appropriateCompare);

L'algorithme optimal ne devrait pas avoir besoin de plus de 1,5 * N - 2 comparaisons. (Une fois que nous avons décidé que c'est O (n), quel est le coefficient devant N? 2 * N comparaisons est inférieur à optimal).

Alors, déterminez d'abord le «gagnant» et le «perdant» dans chaque paire - c'est 0,5 * N comparaisons.

Déterminez ensuite le plus grand élément en comparant les gagnants - c'est une autre comparaison de 0,5 * N-1.

Déterminez ensuite le deuxième plus gros élément en comparant le perdant de la paire où le plus grand élément provenait contre les gagnants de toutes les autres paires - une autre comparaisons de 0,5 * N-1.

Comparaisons totales = 1.5 N - 2.

non testé mais amusant: xxx

Si le plus grand est le premier élément, recherchez le deuxième plus grand de [plus grand + 1, fin). Sinon, recherchez dans [Commencer, plus grand) et [plus grand + 1, fin) et prenez le maximum des deux. Bien sûr, cela a O (2n), donc ce n'est pas optimal.

Si vous avez des itérateurs d'accès aléatoire, vous pouvez le faire comme un tri rapide et utiliser la récursion toujours élégante: xxx

ceci a o (n) et devrait T faire plus de comparaisons que Mise en œuvre de Nomen .