Здравствуйте, kaa.python, Вы писали:

KP>Сложность у решения на range будет, я полагаю что n log n за счет сортировки, ну и в целом будут еще какие-то немаленькие коэффиценты, да и банальные пенальти за память из за перетасовки данных.

Сложность будет выше, т.к. надо будет удалять дубликаты, в std::vector это ооочень не бесплатно.

KP>Только вот в мире за пределами C++ такие вопросы как ты задаешь вообще никого не парят, по вполне себе очевидным причинам — будет тормозить так поправим, главное явной квадратичной и выше сложности не городить.

Да, как-то не хочется получить код на С++, который тормозит на пустом месте. Мы, типа, не привыкли платить за то, что не используем, а тип контейнера и алгоритмы выбираем, исходя из алгоритмической сложности. Неужели этому приходит конец?

KP>Тут сложность решения, я полагаю, будет линейная, единственный вопрос — это коэффициент, но так ли он важен в подавляющем большинстве задач?

Ну, это и правда больше упражнение, благо для матриц сейчас библиотек достаточно и вряд ли кто-то решит писать сам. А необходимость поиска нескольких минимальных/максимальных элементов иногда встречается, реализации из коробки нет, вот и приходится самому думать. Что предлагают делать разработчики на Питоне? Сортировать! На втором месте уже np.argpartition, про который говорят, что он сработает за линейное время, что неверно в общем случае. И только где-то там самый быстрый алгоритм — heapq.nlargest. Хотя именно с кучей можно быстрее всего найти k-top элементов. Не хочется, чтобы С++ уходил в эту же сторону, краткость не решает.