Trova l'elemento più grande e il secondo più grande in un intervallo

Question

Come trovo quanto sopra senza rimuovere l'elemento più grande e cercare di nuovo? C'è un modo più efficiente per farlo? Non importa se questi elementi sono duplicati.

Answer 1

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

Puoi inizializzare largest e second su un limite inferiore appropriato o sui primi due elementi dell'elenco (controlla quale è più grande e non dimenticare di verificare se l'elenco ha almeno due oggetti)

Answer 2

utilizzando partial_sort ?

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

Un esempio:

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 (inizio, inizio + n, fine, confronto) posiziona l'elemento che sarebbe n-en (dove " primo " è " 0th ") se l'intervallo [inizia, fine) sono stati ordinati nella posizione begin + n e si assicura che tutto da [inizio, inizio + n) venga visualizzato prima dell'ennesimo elemento nell'elenco ordinato . Quindi il codice che vuoi è:

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

Questo funzionerà bene nel tuo caso, poiché stai solo cercando i due più grandi. Supponendo che il tuo caso appropriato Confronta le cose dal più grande al più piccolo, il secondo elemento più grande sarà nella posizione 1 e il più grande sarà nella posizione 0.

Answer 4

Supponiamo che tu intenda trovare i due valori univoci più grandi nell'elenco.

Se l'elenco è già ordinato, basta guardare il secondo ultimo elemento (o meglio, scorrere dall'estremità alla ricerca del secondo ultimo valore).

Se l'elenco non è ordinato, non preoccuparti di ordinarlo. L'ordinamento è nella migliore delle ipotesi O (n lg n). L'iterazione lineare semplice è O (n), quindi basta scorrere gli elementi tenendo traccia:

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

Esistono ovviamente altri criteri, che potrebbero essere tutti messi alla prova all'interno del loop. Tuttavia, se intendi dire che dovrebbero essere trovati due elementi che hanno entrambi lo stesso valore più grande, devi considerare cosa succede se tre o più elementi hanno tutti questo valore più grande, o se due o più elementi hanno il secondo più grande.

Answer 5

L'algoritmo ottimale non dovrebbe richiedere più di 1,5 * N - 2 confronti. (Una volta deciso che è O (n), qual è il coefficiente davanti ai confronti di N? 2 * N è meno che ottimale).

Quindi, prima determina il "vincitore" e il "perdente" in ogni coppia - questo è un confronto di 0,5 * N.

Quindi determina l'elemento più grande confrontando i vincitori, ovvero altri 0,5 * N - 1 confronti.

Quindi determina il secondo elemento più grande confrontando il perdente della coppia da cui proviene l'elemento più grande contro i vincitori di tutte le altre coppie - altri 0,5 * N - 1 confronti.

Confronti totali = 1,5 N - 2.

Answer 6

La risposta dipende se vuoi solo i valori, o anche iteratori che puntano ai valori.

Modifica minore della risposta @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

Crea un elenco secondario da n..m, ordinalo in ordine decrescente. Quindi prendi i primi due elementi. Elimina questi elementi dall'elenco originale.

Answer 8

Puoi scansionare la lista in un solo passaggio e salvare il 1o e il 2o valore, che ha un'efficienza O (n) mentre l'ordinamento è O (n log n).

EDIT:
Penso che l'ordinamento parziale sia O (n log k)

Answer 9

Non testato ma divertente:

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

Se il più grande è il primo elemento, cerca il secondo più grande in [più grande + 1, fine). Altrimenti cerca tra [inizio, più grande) e [più grande + 1, fine) e prendi il massimo dei due. Ovviamente, questo ha O (2n), quindi non è ottimale.

Se si dispone di iteratori ad accesso casuale, è possibile eseguire l'ordinamento rapido e utilizzare la ricorsione sempre elegante:

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

Questo ha O (n) e non dovrebbe fare più confronti di Implementazione di NomeN .

Answer 11

top k di solito è leggermente migliore di 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;
    }
  };

Ovviamente il special_allocator può in sostanza essere solo un array di k multiset value_types e un elenco di quei nodi (che in genere non ha nulla su di esso poiché gli altri k sono in uso nel multiset fino al suo è il momento di inserirne uno nuovo e lo cancelliamo e poi lo riutilizziamo immediatamente. Buono avere questo o altrimenti l'allocazione / libera di memoria in std :: multiset e la merda della linea della cache ti uccide. È un (molto) piccolo pezzo di lavoro per dargli uno stato statico senza violare le regole di allocazione STL.

Non buono come un algo specializzato per esattamente 2 ma per fisso & kt; < n , indoverei (2n + delta * n) dove delta è piccolo - il mio DEK ACP vol3 S & amp; S è impacchettato e una stima su delta è un po 'più di lavoro che voglio fare.

il peggiore medio è che indovinerei n (log (k-1) + 2) quando in ordine opposto e tutti distinti.

best è 2n + k (log k) poiché k best è il primo