Найдите самый большой и второй по величине элемент в диапазоне

using partial_sort ?

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

An Example:

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

nth_element (begin, begin + n, end, Compare) помещает элемент, который был бы n-м (где «first» - «0-й»), если бы диапазон [begin, end) был отсортирован в position begin + n и гарантирует, что все из [begin, begin + n) появится перед n-м элементом в отсортированном списке. Итак, код, который вам нужен:

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

Это будет хорошо работать в вашем случае, поскольку вы ищете только два самых больших. Предполагая, что ваш соответствующийCompare сортирует вещи от наибольшего к наименьшему, второй по величине элемент будет в позиции 1, а самый большой будет в позиции 0.

Lets assume you mean to find the two largest unique values in the list.

If the list is already sorted, then just look at the second last element (or rather, iterate from the end looking for the second last value).

If the list is unsorted, then don't bother to sort it. Sorting is at best O(n lg n). Simple linear iteration is O(n), so just loop over the elements keeping track:

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

There are of course other criteria, and these could all be put into the test inside the loop. However, should you mean that two elements that both have the same largest value should be found, you have to consider what happens should three or more elements all have this largest value, or if two or more elements have the second largest.

Ответ зависит от того, нужны ли вам только значения или итераторы, указывающие на значения.

Незначительная модификация @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;
   }
}

Оптимальный алгоритм не должен требовать более 1,5 * N - 2 сравнений. (Как только мы решили, что это O (n), какой коэффициент перед N? 2 * N сравнений меньше оптимального).

Итак, сначала определите «победителя» и «проигравшего» в каждой паре. - это 0,5 * N сравнений.

Затем определите самый большой элемент, сравнивая победителей - это еще одно сравнение 0,5 * N - 1.

Затем определите второй по величине элемент, сравнивая проигравшего из пары, из которой пришел самый большой элемент от победителей всех остальных пар - еще 0,5 * N - 1 сравнений.

Всего сравнений = 1,5 N - 2.

Create a sublist from n..m, sort it descending. Then grab the first two elements. Delete these elements from the orginal list.

You can scan the list in one pass and save the 1st and 2nd values, that has a O(n) efficiency while sorting is O(n log n).

EDIT:
I think that partial sort is O(n log k)

Непроверено, но весело:

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

Если самый большой является первым элементом, ищите второй по величине в [наибольший + 1, конец). В противном случае выполните поиск в [начало, наибольший) и [наибольший + 1, конец) и возьмите максимальное из двух. Конечно, это O (2n), поэтому это не оптимально.

Если у вас есть итераторы с произвольным доступом, вы можете сделать такую ​​же быструю сортировку и использовать элегантную рекурсию:

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

Это O (n) и не должно проводить больше сравнений, чем реализация NomeN .

среднее худшее, я бы предположил, что n (log (k-1) + 2) в противоположном порядке и все разные.

наилучшим является 2n + k (log k), для наилучшего k является первым