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

Question

Как мне найти указанное выше, не удаляя самый большой элемент и не выполняя повторный поиск?Есть ли более эффективный способ сделать это?Не имеет значения, являются ли эти элементы дубликатами.

Answer 1

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

Вы можете инициализировать largest и second соответствующую нижнюю границу или первые два элемента в списке (проверьте, какой из них больше, и не забудьте проверить, есть ли в списке хотя бы два элементы)

Answer 2

используя partal_sort ?

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

Пример:

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 (начало, начало + n, конец, сравнение) помещает элемент, который будет nth (где «first» равно «0»), если диапазон [begin, end) были отсортированы в позиции begin + n и следят за тем, чтобы все из [begin, begin + n) появилось перед n-м элементом в отсортированном списке , Итак, код, который вы хотите:

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

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

Answer 4

Предположим, вы хотите найти два самых больших уникальных значения в списке.

Если список уже отсортирован, просто посмотрите на второй последний элемент (или, скорее, итерируйте с конца, ища второе последнее значение).

Если список не отсортирован, не пытайтесь его отсортировать. Сортировка в лучшем случае O (n lg n). Простая линейная итерация - это O (n), так что просто зацикливайтесь на отслеживании элементов:

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 5

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

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

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

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

Общее количество сравнений = 1,5 N - 2.

Answer 6

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

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

Создайте подсписок из n..m, отсортируйте его по убыванию. Затем возьмите первые два элемента. Удалите эти элементы из оригинального списка.

Answer 8

Вы можете просмотреть список за один проход и сохранить 1-е и 2-е значения, что имеет эффективность O (n), в то время как сортировка равна O (n log n).

Редактировать:
Я думаю, что частичная сортировка равна O (n log k).

Answer 9

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

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

Если наибольшим является первый элемент, найдите второй по величине в [наибольшее + 1, конец). В противном случае ищите в [begin, large) и [large + 1, end) и возьмите максимум из двух. Конечно, это имеет 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 .

Answer 11

top k обычно немного лучше, чем 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;
    }
  };

Конечно, special_allocator по сути может быть просто массивом из k множественных значений-типов и списком этих узлов (в котором обычно ничего нет, так как другие k используются в мультимножестве до тех пор, пока Пришло время вставить новый, и мы стерли, а затем сразу же повторно использовали его. Хорошо иметь это или иначе память, выделяемую / свободную в std :: multiset, и дерьмо строки кэша убивает тебя. Это (очень) крошечная работа придать ему статическое состояние без нарушения правил распределителя STL.

Не так хорошо, как специализированный алгоритм для ровно 2, но для фиксированного k < < < n , я бы УГОВОРИЛ (2n + delta * n), где delta мала - мой DEK ACP vol3 S & amp; S упакован, и оценка дельты - это немного больше работы, которую я хочу сделать.

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

best - это 2n + k (log k), для k лучше всего быть первым