如何获得产生特定总和的top-x元素
How to get top-x elements that result in a specific sum
我想获得总计至少为给定总和的数组的前 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
非常期待您的回答！
如果我们可以有一个中值选择算法，其时间复杂度为 O(n) 的可能性足够大，那么我们可以得到总体 O(n)。请注意，在选择中位数之后，我们只需要检查分区中的一个部分，从而导致 N + N/2 + N/4... 的边界为 O(n)。这是因为想要的总和要么包含在中位数以上的一半中，要么我们需要从下半部分添加更多，在这种情况下我们不需要检查上半部分。
您可以将您的值四舍五入为 3 位小数，并使用 bucket sort。使用 3 位小数，您将需要 1000 个桶。您可以根据您的问题使用更多或更少的桶。时间复杂度为 O(n+k)，其中 k 是桶的数量。
在您的存储桶中，您可以存储准确的值，因此当扫描存储桶以获得所需的总和时，您将使用实际值。你说最高值通常代表所有值的 1%。顶部的桶应该只包含几个值。
我想获得总计至少为给定总和的数组的前 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
非常期待您的回答！
如果我们可以有一个中值选择算法，其时间复杂度为 O(n) 的可能性足够大，那么我们可以得到总体 O(n)。请注意，在选择中位数之后，我们只需要检查分区中的一个部分，从而导致 N + N/2 + N/4... 的边界为 O(n)。这是因为想要的总和要么包含在中位数以上的一半中，要么我们需要从下半部分添加更多，在这种情况下我们不需要检查上半部分。
您可以将您的值四舍五入为 3 位小数，并使用 bucket sort。使用 3 位小数，您将需要 1000 个桶。您可以根据您的问题使用更多或更少的桶。时间复杂度为 O(n+k)，其中 k 是桶的数量。
在您的存储桶中，您可以存储准确的值，因此当扫描存储桶以获得所需的总和时，您将使用实际值。你说最高值通常代表所有值的 1%。顶部的桶应该只包含几个值。