Encontrar más grande y el segundo más grande de elemento en un rango de

Question

¿Cómo puedo encontrar el de arriba sin quitar el elemento más grande y a buscar de nuevo?Es allí 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 largest y second para una adecuada límite inferior, o a los dos primeros elementos de la lista (comprobar que uno es más grande, y no se olvide de comprobar si la lista tiene al menos dos elementos)

Answer 2

utilizando 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 3

nth_element (begin, begin + n, end, Compare) coloca el elemento que sería nth (donde " first " es " 0th ") si el rango [begin, end) se ordenaron en la posición begin + n y se asegura de que todo, desde [begin, begin + n) aparezca antes del enésimo elemento de 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 los dos más grandes. Suponiendo que su Comparación apropiada clasifica 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 4

Supongamos que quiere 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, repita 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). La iteración lineal simple es O (n), así que simplemente recorra los elementos haciendo un seguimiento:

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 todos estos podrían ser puestos a prueba dentro del ciclo. Sin embargo, si quiere decir que se deben encontrar dos elementos que tienen el mismo valor más grande, debe considerar qué sucede si tres o más elementos tienen este valor más grande, o si dos o más elementos tienen el segundo valor más grande.

Answer 5

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

Entonces, primero determine el " ganador " y el "perdedor" en cada par, eso es 0.5 * N comparaciones.

Luego determine el elemento más grande comparando a los ganadores, es decir, otras 0.5 * N - 1 comparaciones.

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

Comparaciones totales = 1.5 N - 2.

Answer 6

La respuesta depende si solo desea los valores, o también iteradores apuntando a los valores.

Modificación menor de @will answer.

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

Cree una sublista desde n..m, ordénela descendente. Luego agarra los dos primeros elementos. Elimine estos elementos de la lista original.

Answer 8

Puede escanear la lista de una vez y guardar los valores primero y segundo, que tienen una eficiencia O (n) mientras que la clasificación es O (n log n).

EDITAR:
Creo que la ordenación parcial es O (n log k)

Answer 9

No probado 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, busque el segundo más grande en [más grande + 1, fin]. De lo contrario, busque en [inicio, mayor) y [mayor + 1, final) 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, puede hacer lo que hace la ordenación rápida y usar la recurrencia siempre 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);
}

Esto tiene O (n) y no debería hacer más comparaciones que Implementación de NomeN .

Answer 11

top k suele ser un poco mejor 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;
    }
  };

Por supuesto, el special_allocator puede ser esencialmente una matriz de k mult_conjunto value_types y una lista de esos nodos (que normalmente no tiene nada, ya que los otros k están en uso en el multiset hasta su es hora de poner uno nuevo y lo borramos y luego lo reutilizamos de inmediato. Es bueno tener esto o la memoria asignada / libre en std :: multiset y la basura de la línea de caché te mata. Es un trabajo (muy) muy pequeño para darle un estado estático sin violar las reglas del asignador STL.

No es tan bueno como un algoritmo especializado para exactamente 2 pero para k < < n fijo, GUESS (2n + delta * n) donde delta es pequeño: mi DEK ACP vol3 S & amp; S está empaquetado y una estimación del 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 orden opuesto y todo distinto.

mejor es 2n + k (log k) para que k sea el primero