Максимальное количество элементов, сумма которых меньше, чем цель в несортированном массиве (без сортировки)

Question

Я работаю над вопросом алгоритма, который выглядит следующим образом:

Массив (элементов) действительных чисел в произвольном несортированном порядке, найти максимальное количество элементов, сумма которых меньше, чем целевое значение за O (n) времени. Поэтому сортировка не допускается.

Думаю, мне следует использовать алгоритм Randomized QuickSelect, который находит K-й элемент в несортированном массиве в O (n). Я хочу знать, какую правильную модификацию в алгоритме Randomized QuickSelect можно использовать для моего вопроса?

Answer 1

В алгоритме рандомизированного быстрого выбора массив разделяется на случайное значение позиции. Нижняя часть раздела содержит все значения, меньшие, чем это рандомизированное значение позиции, а верхняя часть содержит все значения, превышающие это рандомизированное значение позиции. Для вашей задачи вы вычислите сумму этого нижнего массива разделов. Теперь, если сумма меньше целевого значения, выберите случайное значение позиции из верхнего раздела и снова запустите алгоритм разделения. Если сумма превышает целевое значение, выберите случайное значение позиции из нижнего раздела и снова запустите алгоритм разделения. Продолжайте, пока не найдете ответ. Обратите внимание, что в худшем случае это может быть O (n ^ 2).