python - 如何获取导致特定总和的 top-x 元素
问题描述
我想得到一个数组的前 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)。这是因为想要的总和要么包含在中位数上方的一半中,要么我们需要从下半部分添加更多,在这种情况下,我们不需要检查上半部分。
推荐阅读
- javascript - 如何从 Android WebView 的标题中获取表单数据?
- xml - 将 XML Payload 发布到服务器以检索值
- docker - 如何将 sslmode=require 传递给 liquibase
- spring-boot - Springfox Boot Starter 3.0.0 JsonSerializer 错误
- azure - NLogViewer UDP 目标在 Azure 服务经典中保持静默
- javascript - 从道具内部的redux访问状态更改,状态成功更改,但该对象的道具未定义
- sql - 我可以在 SparkSQL 中使用 LATERAL VIEW 和 STACK 函数吗?
- angular - 数组按月和日分组
- git - Gitlab 存储库无法识别我的用户名信息
- c# - Polly 在重试时更改查询字符串