如何获取导致特定总和的top-x元素

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

您可以将值四舍五入为3位十进制数字，并使用桶排序。使用3位十进制数字，您将需要1000个桶。您可以根据您的问题使用更多或更少的桶。时间复杂度将为O（n k），其中k是桶数。

在存储桶中，您可以存储确切的值，因此在扫描存储桶以获取所需总和时，您将使用实际值。您说最高值通常代表所有值的1%。然后，顶部存储桶应仅包含几个值。

Answer 2

如果我们可以有一个中位数选择算法，它的时间复杂度为O（n），那么我们可以得到总体O（n）。观察到，在选择中位数后，我们只需要检查分区中的一个部分，从而得出N/2 N/4…的界为O（N）。这是因为想要的总和要么包含在中位数以上的一半中，要么我们需要从下半部分添加更多，在这种情况下，我们不需要检查上半部分。