gpt4 book ai didi

python - 如何获得产生特定总和的top-x元素

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:15:59 25 4
gpt4 key购买 nike

我想获得一个数组的前 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)。这是因为想要的总和包含在中位数以上的一半中,或者我们需要从下半部分添加更多,在这种情况下我们不需要检查上半部分。

关于python - 如何获得产生特定总和的top-x元素,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/56440832/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com