Найти самый большой и второй по величине элемент в диапазоне
Как мне найти вышеупомянутое без удаления самого большого элемента и повторного поиска? Есть ли более эффективный способ сделать это? Не имеет значения, являются ли эти элементы дубликатами.
12 ответов
for (e: all elements) {
if (e > largest) {
second = largest;
largest = e;
} else if (e > second) {
second = e;
}
}
Вы можете либо инициализировать largest а также second до соответствующей нижней границы или до первых двух элементов в списке (проверьте, какой из них больше, и не забудьте проверить, есть ли в списке хотя бы два элемента)
Используя part_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];
nth_element(begin, begin+n,end,Compare) помещает элемент, который будет nth (где "first" равно "0th"), если диапазон [begin, end) были отсортированы в позиции begin+n и убедитесь, что все из [begin,begin+n) появится перед n-м элементом в отсортированном списке. Итак, код, который вы хотите:
nth_element(container.begin(),
container.begin()+1,
container.end(),
appropriateCompare);
Это будет хорошо работать в вашем случае, так как вы ищете только два крупнейших. Предполагая, что ваш assignCompare сортирует вещи от наибольшего к наименьшему, второй по величине элемент будет с позицией 1, а самый большой будет с позицией 0.
Предположим, вы хотите найти два самых больших уникальных значения в списке.
Если список уже отсортирован, просто посмотрите на второй последний элемент (или, скорее, итерируйте с конца, ища второе последнее значение).
Если список не отсортирован, не пытайтесь его отсортировать. Сортировка в лучшем случае 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;
}
Конечно, есть и другие критерии, и все они могут быть проверены внутри цикла. Однако, если вы имеете в виду, что должны быть найдены два элемента, оба из которых имеют одинаковое наибольшее значение, вы должны рассмотреть, что произойдет, если все три или более элемента имеют это наибольшее значение, или если два или более элемента имеют второе по величине значение.
Оптимальный алгоритм не должен требовать более 1,5 * N - 2 сравнений. (Как только мы решили, что это O(n), какой коэффициент перед N? 2 * N сравнениями меньше оптимального).
Итак, сначала определите "победителя" и "проигравшего" в каждой паре - это 0,5 * N сравнений.
Затем определите самый большой элемент, сравнивая победителей - это еще 0,5 * N - 1 сравнения.
Затем определите второй по величине элемент, сравнив проигравшего в паре, из которого был получен самый большой элемент, с победителями всех остальных пар - еще 0,5 * N - 1 сравнение.
Всего сравнений = 1,5 Н - 2.
Ответ зависит от того, хотите ли вы просто значения или итераторы, указывающие на значения.
Незначительная модификация ответа @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;
}
}
Я думаю, вы могли бы реализовать собственный массив и перегрузить индексированные методы получения/установки элементов. Затем при каждом вызове набора сравнивайте новое значение с двумя полями для результата. Хотя это делает сеттер медленнее, он выигрывает от кэширования или даже регистрации. Тогда нет возможности получить результат. Это должно быть быстрее, если вы заполняете массив только один раз при нахождении максимумов. Но если массив часто модифицируется, то он работает медленнее.
Если массив используется в векторизованных циклах, его становится сложнее реализовать, поскольку вам нужно использовать оптимизированные методы max avx/sse внутри сеттера.
Если наибольшим является первый элемент, ищите второй по величине в [наибольший +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.
Создайте подсписок из n..m, отсортируйте его по убыванию. Затем возьмите первые два элемента. Удалите эти элементы из оригинального списка.
Вы можете просмотреть список за один проход и сохранить 1-е и 2-е значения, которые имеют эффективность O(n), а сортировка - O(n log n).
РЕДАКТИРОВАТЬ:
Я думаю, что частичная сортировка O(n log k)
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 множественного набора value_types и список этих узлов (в котором обычно ничего нет, так как другие k используются в мультимножестве, пока не настало время вставить новый, и мы удалим, а затем сразу использовать его. Хорошо иметь это или иначе память, выделяемую / свободную в std::multiset и хрень строки кэша убивает тебя. Это (очень) крошечная работа, чтобы дать ему статическое состояние без нарушения правил распределителя STL.
Не так хорошо, как специализированный алгоритм для ровно 2, но для фиксированной k<<nЯ бы УГОВОРИЛ (2n+delta*n), где delta мала - мой DEK ACP vol3 S&S упакован, а оценка delta - это немного больше работы, которую я хочу сделать.
среднее худшее, я бы догадался n(log(k-1) + 2), когда в противоположном порядке и все различно.
лучший - это 2n + k(log k) для 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;
}