Алгоритм нахождения m наименьших чисел в списке из n чисел

Question

Мне нужно написать алгоритм, чтобы найти «m наименьших чисел в списке из n чисел». Я не понимаю, что означает эта строка. Нужно ли искать все самые маленькие числа в списке и распечатывать их. Например, если у меня есть список, скажем, 4 элемента [10, 20, 30, 40], должен ли я печатать каждое число, меньшее 40, по одной итерации за раз. Или есть какой-то другой смысл, который ускользает от меня.

Answer 1

То, что они спрашивают, это: учитывая список из n чисел, найдите m наименьших чисел. Поэтому, если n = 10 и m = 5, а список такой:

 Input: 1 4 2 6 3 6 2 4 6 1
Output: 1 1 2 2 3

Решение этой проблемы состоит в заполнении max-heap первыми m числами из набора из n чисел. Затем go просмотрите оставшиеся номера нм в списке и сравните с максимумом максимальной кучи. Если число из списка меньше максимального из списка максимальных значений, удалите максимальное из списка максимальных и замените его текущим числом из списка. Повторяйте до тех пор, пока все числа не будут проверены, а затем верните элементы в m-куче.

Сложность этого - O (nlogm), поскольку вы потенциально можете сделать одно удаление и одну вставку для каждого из элементов (nm) в списке после взятия первого m для добавления максимальной кучи.

Answer 2

Что я понимаю, так это то, что вам нужно написать функцию, которая принимает в качестве параметра число m и возвращает массив чисел, размер которого m и содержит наименьшие числа m.
Принимая ваш пример , если мы скажем, что m равно 2, мы вернем массив из 2 элементов, содержащий 2 наименьших элемента: [10,20]
Если мы установим m в 3, функция вернет [10,20,30]