Как получить топ-х элементов, которые приводят к определенной сумме

Question

Я хотел бы получить верхние X элементов массива, которые суммируют, по крайней мере, до заданной суммы, не сортируя весь массив заранее по линейному времени. Я думаю, что невозможно получить линейное время во всех случаях, но, по крайней мере, в моих входных массивах у меня есть примерно 1% элементов, которые составляют 99% суммы. И мне нужно правильно их идентифицировать. Я не знаю, помогает ли это, но сумма всех элементов всегда равна 1.

Я уже реализовал это с отсортированным массивом, но это взрывает сложность моего алгоритма. Впоследствии я уже изучил алгоритм top-k и алгоритм рюкзака, но они не позволяют гибким элементам x зависеть от заданной минимальной суммы.

Input Array: [0.1, 0.2, 0.4, 0.05, 0.01, 0.01, 0.01, 0.02, 0.15, 0.05]

Example 1:

Given Sum: 0.8

Expected output [0.1, 0.2, 0.4, 0.15, ] --> Sum 0.85 but only top 4 elements

Example 2: 

Given Sum: 0.95

Expected output [0.1, 0.2, 0.4, 0.15, 0.05, 0.05 ] --> Sum 0.95 but only top 6 elements

Очень жду ваших ответов!

Answer 1

Если у нас может быть алгоритм выбора медианы с достаточно высокой вероятностью того, что его временная сложность составляет O (n), то мы можем иметь общее O (n). Заметьте, что после выбора медианы нам нужно исследовать только одну из частей в разделе, что приводит к N + N / 2 + N / 4 ... с границей O (n). Это потому, что искомая сумма либо содержится в половине над медианой, либо нам нужно добавить больше из нижней половины, и в этом случае нам не нужно проверять верхнюю половину.

Answer 2

Вы можете округлить свои значения, чтобы сказать 3 десятичных знака, и использовать сортировку сегмента . С 3 десятичными цифрами вам понадобится 1000 ведер. Вы можете использовать больше или меньше ведер в зависимости от вашей проблемы. Временная сложность будет O (n + k), где k - количество сегментов.

В ваших корзинах вы можете хранить точные значения, поэтому при сканировании корзин для получения желаемой суммы вы будете использовать фактические значения. Вы сказали, что верхние значения обычно представляют 1% от всех значений. Верхние сегменты должны содержать только несколько значений.