Trouver le plus grand et le deuxième plus grand élément d'une gamme

Question

Comment trouver ce qui précède sans supprimer le plus grand élément et effectuer une nouvelle recherche? Y a-t-il un moyen plus efficace de le faire? Peu importe que ces éléments soient des doublons.

Answer 1

for (e: all elements) {
 if (e > largest) {
   second = largest;
   largest = e;
 } else if (e > second) {
   second = e;
 }
}

Vous pouvez initialiser largest et second sur une limite inférieure appropriée ou sur les deux premiers éléments de la liste (cochez celui qui est le plus grand et n'oubliez pas de vérifier si la liste en contient au moins deux). éléments)

Answer 2

en utilisant partial_sort ?

std::partial_sort(aTest.begin(), aTest.begin() + 2, aTest.end(), Functor);

Un exemple:

std::vector<int> aTest;

    aTest.push_back(3);
    aTest.push_back(2);
    aTest.push_back(4);
    aTest.push_back(1);


    std::partial_sort(aTest.begin(), aTest.begin()+2,aTest.end(), std::greater<int>());

    int Max = aTest[0];
int SecMax = aTest[1];

Answer 3

nth_element (begin, begin + n, end, Compare) place l'élément qui serait nth (où "premier" est "0ème") si l'intervalle [début, fin) ont été triés à la position begin + n et vérifie que tout ce qui vient de [begin, begin + n) apparaît 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);

Cela fonctionnera bien dans votre cas, puisque vous ne recherchez que les deux plus gros. En supposant que votre critère de comparaison approprié trie les éléments du plus grand au plus petit, le deuxième plus grand élément étant en position 1 et le plus grand en position 0.

Answer 4

Supposons que vous vouliez trouver les deux plus grandes valeurs uniques de la liste.

Si la liste est déjà triée, regardez simplement l'avant-dernier élément (ou plutôt, parcourez la liste à la fin en recherchant l'avant-dernière valeur).

Si la liste n'est pas triée, ne vous occupez pas de la trier. Le tri est au mieux O (n lg n). L'itération linéaire simple est O (n), il suffit donc de parcourir les éléments en gardant la trace:

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

Il existe bien sûr d’autres critères, qui pourraient tous être mis à l’essai à l’intérieur de la boucle. Cependant, si vous voulez dire que deux éléments qui ont la même valeur la plus grande doivent être trouvés, vous devez considérer ce qui se passe si trois éléments ou plus ont tous la plus grande valeur, ou si deux ou plus ont le deuxième plus grand.

Answer 5

L’algorithme optimal ne devrait pas nécessiter 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, la comparaison est moins optimale).

Alors, déterminez d’abord le " gagnant " et le "perdant" dans chaque paire - soit 0,5 * N comparaisons.

Ensuite, déterminez l’élément le plus important en comparant les gagnants - c’est encore 0,5 * N - 1 comparaisons.

Ensuite, déterminez le deuxième élément en importance en comparant le perdant de la paire dont l’élément le plus important provient des gagnants de toutes les autres paires - une comparaison supplémentaire de 0,5 * N - 1.

Comparaisons totales = 1,5 N - 2.

Answer 6

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

Modification mineure de la réponse @will.

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

Answer 7

Créez une sous-liste à partir de n..m, triez-la par ordre décroissant. Ensuite, prenez les deux premiers éléments. Supprimez ces éléments de la liste d'origine.

Answer 8

Vous pouvez parcourir la liste en une seule passe et enregistrer les première et deuxième valeurs ayant une efficacité de O (n) lors du tri: O (n log n).

EDIT:
Je pense que cette sorte partielle est O (n log k)

Answer 9

Non testé mais amusant:

template <typename T, int n>
class top_n_functor : public unary_function<T, void>
{

  void operator() (const T& x) {
     auto f = lower_bound(values_.begin(), values_.end(), x);

     if(values_.size() < n) {
         values_.insert(f, x);
         return;
     }

     if(values_.begin() == f)
          return;

     auto removed = values_.begin();
     values_.splice(removed, values_, removed+1, f);

     *removed = x;
  }

  std::list<T> values() {
     return values_;
  }
private:
   std::list<T> values_;
};

int main()
{
  int A[] = {1, 4, 2, 8, 5, 7};
  const int N = sizeof(A) / sizeof(int);

  auto vals = for_each(A, A + N, top_n_functor<int,2>()).values();

  cout << "The top is " << vals.front()
       << " with second place being " << *(vals.begin()+1) << endl;
}

Answer 10

Si le plus grand est le premier élément, recherchez le deuxième plus grand dans [plus grand + 1, fin). Sinon, cherchez dans [début, le 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 à accès aléatoire, vous pouvez faire un tri rapide et utiliser la récursion toujours élégante:

template< typename T >
std::pair<T,T> find_two_largest(const std::pair<T,T>& lhs, const std::pair<T,T>& rhs)
{
  // implementation finding the two largest of the four values left as an exercise :) 
}

template< typename RAIter >
std::pair< typename std::iterator_traits<RAIter>::value_type
         , typename std::iterator_traits<RAIter>::value_type > 
find_two_largest(RAIter begin, RAIter end)
{
  const ptr_diff_t diff = end-begin;
  if( diff < 2 )
    return std::make_pair(*begin, *begin);
  if( diff < 3 )
    return std::make_pair(*begin, *begin+1);
  const RAIter middle = begin + (diff)/2;
  typedef std::pair< typename std::iterator_traits<RAIter>::value_type
                   , typename std::iterator_traits<RAIter>::value_type > 
    result_t;
  const result_t left = find_two_largest(begin,middle);
  const result_t right = find_two_largest(middle,end);

  return find_two_largest(left,right);
}

Ceci a O (n) et ne devrait pas faire plus de comparaisons que Implémentation de NomeN .

Answer 11

top k est généralement un peu meilleur que n (log k)

 template <class t,class ordering>
 class TopK {
 public:
    typedef std::multiset<t,ordering,special_allocator> BEST_t;
    BEST_t best;
    const size_t K;
    TopK(const size_t k)
        : K(k){
    } 
    const BEST_t& insert(const t& item){
        if(best.size()<k){
            best.insert(item);
            return best;
        }
        //k items in multiset now
        //and here is why its better - because if the distribution is random then
        //this and comparison above are usually the comparisons that is done; 
        if(compare(*best.begin(),item){//item better than worst
           erase(begin());//the worst
           best.insert(item); //log k-1 average as only k-1 items in best
        } 
        return best;
    } 
    template <class it>
    const BEST_t& insert(it i,const it last){
        for(;i!=last;++i){
            insert(*i);    
        }
        return best;
    }
  };

Bien sûr, special_allocator peut être essentiellement un tableau de k multiset value_types et une liste de ces nœuds (qui n'ont généralement rien dessus, car les autres k sont utilisés dans le multiset jusqu'à ce que sa Il est temps d’en installer un nouveau et de le supprimer puis de le réutiliser immédiatement. C’est bien d’avoir cela ou bien la mémoire alloc / free dans std :: multiset et la foutue ligne de cache vous tue. C’est un (très) minuscule travail. pour lui donner un état statique sans violer les règles de l'allocateur STL.

Pas aussi bon qu'un algo spécialisé pour exactement 2, mais pour un fixe , , je devinerais (2n + delta * n) où delta est petit - mon DEK ACP vol3 S & amp; S est emballé et une estimation sur delta est un peu plus de travail que je veux faire.

la pire moyenne est je suppose que n (log (k-1) + 2) est dans l’ordre opposé et est tout à fait distinct.

mieux vaut 2n + k (log k) pour le k meilleur étant le premier