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

Question

Come trovo quanto sopra senza rimuovere l'elemento più grande e ricominciare la ricerca? 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; 
} 
} 

Si potrebbe o inizializzare largest e second ad un adeguato limite inferiore, o per i primi due elementi nell'elenco (verificare che uno è più grande, e non dimenticare di controllare se la lista ha almeno due articoli)

Answer 2

Creare una sottolista da n..m, ordinarla in modo discendente. Quindi prendi i primi due elementi. Elimina questi elementi dall'elenco originale.

Answer 3

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 4

lascia supporre si intende per trovare i due più grandi valori unici nella lista.

Se la lista è già ordinata, basta guardare il penultimo elemento (o meglio, scorrere dalla fine alla ricerca del penultimo valore).

Se l'elenco non è ordinato, non preoccuparsi di ordinarlo. L'ordinamento è al massimo O (n lg n). Semplice iterazione lineare è O (n), quindi basta ciclo sugli 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; 
    } 

Ci sono naturalmente altri criteri, e queste potrebbero tutti essere messo in prova all'interno del ciclo. Tuttavia, dovresti intendere che due elementi che hanno entrambi lo stesso valore più grande dovrebbero essere trovati, 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

È possibile eseguire la scansione dell'elenco in un passaggio e salvare il 1 ° e il 2 ° valore, che ha un'efficienza O (n) mentre l'ordinamento è O (n log n).

EDIT:
penso che sorta parziale è O (n log k)

Answer 6

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

Modifica minore di @risposta.

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

nth_element (inizio, cominciano + n, fine, Confronta) pone l'elemento che sarebbe ennesima (dove "prima" è "0a") se il campo [inizio, fine) sono stati ordinati in posizione iniziare + n e si assicura che tutto da [begin, begin + n) venga visualizzato prima dell'ennesimo elemento nell'elenco ordinato. Quindi il codice che si desidera è:

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

questo funzionerà bene nel tuo caso, dal momento che si sta solo cercando il due più grandi. Supponendo che yourCompare appropriato generi 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 8

L'algoritmo ottimale non dovrebbe richiedere più di 1.5 * N-2 confronti. (Una volta che abbiamo deciso che è O (n), qual è il coefficiente di fronte a N? 2 * N i confronti non sono ottimali).

Quindi, per prima cosa determinare il "vincitore" e il "perdente" in ogni coppia - questo è 0.5 * N confronti.

Quindi determinare l'elemento più grande confrontando i vincitori - questo è un altro 0,5 * N - 1 confronti.

Quindi determinare il secondo elemento più grande confrontando il perdente della coppia in cui l'elemento più grande è venuto da contro i vincitori di tutte le altre coppie - un altro 0,5 * N - 1 confronti.

confronti Totale = 1,5 N - 2.

Answer 9

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 la più grande è il primo elemento, cercare il secondo più grande in [grande + 1, end). Altrimenti cerca in [inizio, più grande) e [più grande + 1, fine) e prendi il massimo dei due. Naturalmente, questo ha O (2n), quindi non è ottimale.

Se si dispone di iteratori ad accesso casuale, si potrebbe fare come quick sort fa e utilizzare il sempre elegante ricorsione:

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 NomeN's implementation.

Answer 11

superiore k è di solito un po 'più di n (k log)

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

Naturalmente il special_allocator può sostanzialmente essere solo un array di k value_types multiset e un elenco di tali nodi (che tipicamente ha nulla su di esso mentre gli altri k sono in uso nel multiset fino al momento in cui ne inseriamo uno nuovo e lo cancelliamo e quindi lo riusciamo immediatamente a riutilizzare. Buono avere questo o altrimenti allocare/liberare memoria in std :: multiset e nella cache line crap kills ya. È un (molto) piccolo pezzo di lavoro per dargli stato statico senza violare le regole di allocatore STL

Non buono come specialista ed algo esattamente per 2 ma per fisso k<<n, vorrei GUESS (2n + delta * n) dove delta è piccolo - il mio volk DEK ACP S & S è impacchettato e una stima su delta è un po 'più di lavoro che voglio fare .

medio peggiore è che indicherei n (log (k-1) + 2) quando nell'ordine opposto e tutti distinti.

migliore è 2n + k (k log) per il miglior k essendo il primo