Encontre o maior e segundo maior elemento em um intervalo

Question

Como faço para encontrar o acima sem remover o maior elemento e pesquisar novamente? Existe uma maneira mais eficiente de fazer isso? Não importa se os estes elementos são duplicados.

Answer 1

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

Você poderia largest quer inicializar e second a um apropriado limite inferior, ou para os dois primeiros itens da lista (verifique qual é o maior, e não se esqueça de verificar se a lista tem pelo menos dois itens)

Answer 2

partial_sort ?

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

Um exemplo:

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

lugares nth_element(begin, begin+n,end,Compare) o elemento que seria n (em que "primeiro" é "0"), se o [begin, end) gama foram classificadas na posição begin+n e garante que tudo, desde [begin,begin+n) iria comparecer perante o enésimo elemento na lista ordenada. Assim, o código que você quer é:

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

Este vai funcionar bem no seu caso, já que você só está procurando os dois maiores. Assumindo que o seu appropriateCompare ordena as coisas de maior para o menor, o segundo maior elemento com estar na posição 1 ea maior será na posição 0.

Answer 4

Vamos supor que você quer dizer para encontrar os dois maiores valores exclusivos na lista.

Se a lista já está classificado, em seguida, basta olhar para o segundo último elemento (ou melhor, iterate a partir do final olhando para o segundo último valor).

Se a lista é não classificado, em seguida, não se preocupam em resolver isso. Triagem é na melhor das hipóteses O (n lg n). Simples linear iteração é O (n), então apenas loop sobre os elementos manter o controle:

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

Há, naturalmente, outros critérios, e estes poderiam ser colocados no teste dentro do loop. No entanto, você deve significar que dois elementos que ambos têm o mesmo valor maior deve ser encontrado, você tem que considerar o que acontece deve três ou mais elementos todos têm este maior valor, ou se dois ou mais elementos tem a segunda maior.

Answer 5

O algoritmo optimal não deve precisar de mais do que 1,5 * N - 2 comparações. (Uma vez que nós decidimos que é O (n), que é o coeficiente na frente de N? 2 * N comparações é abaixo do ideal).

Assim, em primeiro lugar determinar o "vencedor" e do "perdedor" em cada par -. Que é 0,5 * N comparações

Em seguida, determinar o maior elemento comparando vencedores - que é mais 0,5 * N -. 1 comparações

Em seguida, determinar a segunda maior elemento comparando o perdedor do par em que o maior elemento de veio contra os vencedores de todos os outros pares - mais 0,5 * N -. 1 comparações

Total de comparações = 1,5 n -. 2

Answer 6

A resposta depende se você quiser apenas os valores, ou também iterators apontando para os valores.

pequena modificação de @will resposta.

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

Criar uma sub-lista de n..m, classificá-lo descer. Em seguida, pegue os dois primeiros elementos. Excluir esses elementos da lista original.

Answer 8

Você pode verificar a lista em uma única passagem e salvar o 1º e 2º valores, que tem um O (n) a eficiência durante a classificação é O (n log n).

EDIT:
Eu acho que esse tipo parcial é O (n log k)

Answer 9

Não testado, mas 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

Se o maior é o primeiro elemento, procure o segundo maior [maior + 1, fim). procurar em contrário [começar, maior) e [maior + 1, final) e tomar o máximo dos dois. Claro, isso tem O (2n), por isso não é ideal.

Se você tem iteradores de acesso aleatório, você poderia fazer como uma espécie rápida faz e usar a recursão 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);
}

Isto tem O (n) e não deve fazer mais comparações que O nomen implementação .

Answer 11

topo k é geralmente um pouco melhor do que o 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;
    }
  };

Claro que o special_allocator pode, em essência, ser apenas um conjunto de k multiset value_types e uma lista desses nós (que normalmente não tem nada sobre ele como o outro k estão em uso no multiset até sua hora de colocar um novo em e nós apagar e, em seguida, imediata ly reutilizá-lo. É bom ter isso ou então a alocação de memória / livre em std :: multiset e a porcaria linha de cache mata ya. É um (muito) pouco de trabalho para dar-lhe estado estático sem violar regras STL alocador.

Não é tão bom como uma especializada algo para exatamente 2 mas para k<<n fixo, eu acho (2n + delta * n), onde delta é pequeno - meu DEK ACP Vol3 S & S é embalado de distância e uma estimativa sobre delta é um pouco mais trabalho que eu quero fazer.

média é pior que suporia n (log (k-1) + 2), quando na ordem oposta e todos distintos.

melhor é 2n + k (log k) para o k melhor ser o primeiro