«Лучший» (идиоматический) способ выбрать k наименьших элементов из контейнера в C++ [дубликат]

На этот вопрос уже есть ответы здесь:

Извлечение 100 лучших чисел из ста миллионов номеров(12 ответов)

Закрыто 2 года назад.

Я довольно часто сталкиваюсь с этой проблемой: по заданной последовательности найти k-наименьший элемент. Вопрос не такой сложный, но я ищу «идиоматический» способ сделать это, который одновременно безопасен ( мало места для ошибок) и которые хорошо сообщают о намерениях. Таким образом, в конечном итоге выполняется сортировка последовательности, затем взятие первого k элемента:

std::sort(container.begin(),container.end());
std::vector k_smallest(container.begin(),container.begin() + k);

Это кажется мне и безопасным, и простым для понимания, но здесь сложность составляет nlogn + k, а не просто n. Как вы, ребята, это делаете, есть ли идоматический способ (используя какую-то непонятную функцию из возможно), который дал бы оптимальную сложность без необходимости повторной реализации колеса

задан amit 14 March 2012 в 15:08

0 ответов

Другие вопросы по тегам:

algorithm stl stl-algorithm c++

«Лучший» (идиоматический) способ выбрать k наименьших элементов из контейнера в C++ [дубликат]

0 ответов

Похожие вопросы: