我希望能够在线性时间内获取数组中至少总和为给定值的前X个元素,而不事先对整个数组进行排序。我认为在所有情况下都无法实现线性时间,但至少在我的输入数组中,大约有1%的元素占据了99%的总和。我需要正确识别这些元素。我不知道这是否有所帮助,但所有元素的总和始终为1。
我已经使用排序后的数组实现了它,但这使得我的算法的复杂性增加了。之后,我已经研究了最高k项算法和背包算法,但它们不允许具有基于给定最小总和的灵活X元素。
我已经使用排序后的数组实现了它,但这使得我的算法的复杂性增加了。之后,我已经研究了最高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
非常期待您的答案!