Encuentra el elemento más grande y el segundo más grande en un rango

Question

¿Cómo puedo encontrar lo anterior sin quitar el elemento más grande y buscar de nuevo? ¿Hay una manera más eficiente de hacer esto? No importa si estos elementos son duplicados.

Answer 1

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

Usted podría inicializar y largestsecond a una cota inferior adecuada, o para los dos primeros elementos de la lista (comprobar cuál es el más grande, y no se olvide de comprobar si la lista tiene al menos dos elementos)

Answer 2

Cree una sublista de n..m, oriéntela descendiendo. Luego toma los primeros dos elementos. Eliminar estos elementos de la lista original.

Answer 3

usando partial_sort?

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

Un ejemplo:

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

Asumamos que quiere decir para encontrar los dos valores únicos más grandes de la lista.

Si la lista ya está ordenada, simplemente mire el segundo último elemento (o más bien, itere desde el final buscando el segundo último valor).

Si la lista no está ordenada, no se moleste en ordenarla. La clasificación es en el mejor de los casos O (n lg n). iteración lineal simple es O (n), por lo que sólo un bucle sobre los elementos de mantenimiento de pista:

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

Por supuesto, hay otros criterios, y estos podrían todos ser puesto en la prueba dentro del bucle. Sin embargo, si quiere decir que deben encontrarse dos elementos que tienen el mismo valor más grande, debe considerar qué sucede si tres o más elementos tienen el mayor valor o si dos o más elementos tienen el segundo valor más grande.

Answer 5

Puede escanear la lista de una pasada y guardar los valores 1º y 2º, que tienen una eficacia O (n) mientras la ordenación es O (n log n).

EDIT:
creo que ese tipo parcial es O (n log k)

Answer 6

La respuesta depende de si sólo desea que los valores, o también iteradores que señalan en los valores.

Modificación menor de la respuesta @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

nth_element (comienza, comienzan + n, final, de comparación) coloca el elemento que sería n (donde "primero" es "0 ª") si el rango [begin, end) se clasificaron en la posición comienzan + ny se asegura de que todo desde [begin, begin + n) aparezca antes del enésimo elemento en la lista ordenada. Entonces el código que desea es:

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

Esto funcionará bien en su caso, ya que solo está buscando las dos más grandes. Suponiendo que su apropiadoCompare ordena las cosas de mayor a menor, el segundo elemento más grande estará en la posición 1 y el más grande estará en la posición 0.

Answer 8

El algoritmo óptimo no debería necesitar más de 1.5 * N - 2 comparaciones. (Una vez que hemos decidido que es O (n), ¿cuál es el coeficiente frente a las comparaciones N? 2 * N es menos que óptimo).

Por lo tanto, primero determine el "ganador" y el "perdedor" en cada par - eso es 0.5 * N comparaciones.

A continuación, determine el elemento más grande comparando los ganadores, es decir, otras 0.5 * N - 1 comparaciones.

Luego determine el segundo elemento más grande comparando el perdedor del par de donde vino el elemento más grande contra los ganadores de todos los otros pares: otras 0.5 * N - 1 comparaciones.

totales comparaciones = 1,5 N - 2.

Answer 9

No comprobado pero divertido:

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 el más grande es el primer elemento, la búsqueda de la segunda más grande de [más grande + 1, final). De lo contrario, busque en [begin, largest) y [largest + 1, end] y tome el máximo de los dos. Por supuesto, esto tiene O (2n), por lo que no es óptimo.

Si tiene iteradores de acceso aleatorio, se puede hacer como una especie rápida y no utilizar la siempre elegante recursividad:

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

Esto tiene O (n) y no debe hacer más comparaciones de NomeN's implementation.

Answer 11

k superior es generalmente un poco mejor que 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; 
    } 
    }; 

Por supuesto, el special_allocator puede en esencia ser sólo un conjunto de value_types multiconjuntos k y una lista de los nodos (que normalmente no tiene nada en él ya que los otros k están en uso en el multiset hasta que sea hora de poner uno nuevo y borrarlo y luego reutilizarlo inmediatamente. Es bueno tener esto o la memoria alloc/free en std :: multiset y el caché la mierda de línea te mata. Es un (muy) pequeño trabajo para darle un estado estático sin violar las reglas de asignación de STL.

No es tan bueno como un specializ ed algo para exactamente 2 pero para k<<n fijo, GUESS (2n + delta * n) donde delta es pequeño - mi DEK ACP vol3 S & S está empaquetado y una estimación en delta es un poco más de trabajo que quiero hacer .

el peor promedio es Supongo que n (log (k-1) + 2) cuando está en el orden opuesto y todo distinto.

mejor es 2n + k (k log) para la mejor k ser la primera