如何获取特定总和的前x个元素

Question

我希望能够在线性时间内获取数组中至少总和为给定值的前X个元素，而不事先对整个数组进行排序。我认为在所有情况下都无法实现线性时间，但至少在我的输入数组中，大约有1%的元素占据了99%的总和。我需要正确识别这些元素。我不知道这是否有所帮助，但所有元素的总和始终为1。

我已经使用排序后的数组实现了它，但这使得我的算法的复杂性增加了。之后，我已经研究了最高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

非常期待您的答案！

- MadMat

---

排序数组如何“增加复杂性”？ O(nlogn) 仅比 O(n) 高一点点。肯定远小于背包问题。 - tobias_k

嗨，Tobias，你是对的，但是 top-k 算法的时间复杂度是 O(log n)，对吧？所以我想知道是否可以在不事先对列表进行排序的情况下做些什么。如果这在 O(log n) 或 O(n) 复杂度下是可能的，有什么想法吗？ - MadMat

不确定您具体指的是哪种 top-k 算法，但即使在无序列表中找到 top-1 元素也不能达到 O(log n)，因为您基本上必须至少查看每个元素一次。 - tobias_k

是的，你说得对，这是我的误解。在基于堆的版本中，您需要O（n log k）。我的问题是我事先不知道k（我称之为x），因为它取决于数组中的值和我想要达到的总和。我考虑了一些东西： 1.选择元素直到达到总和 2.遍历剩余的数组，每当检测到一个大于您的前x个列表中的元素的元素时，将该元素放入并且删除其他元素，这些元素通过添加更大的元素来获得收益。 - MadMat

我不确定我理解了。X和总和都是已知的吗？ - RobertBaron

Answer 1

如果我们能够使用具有足够好的概率的中位数选择算法，其时间复杂度为O(n)，那么我们就可以实现整体O(n)。观察到在选择中位数之后，我们只需要检查分区中的其中一个部分，导致N + N/2 + N/4...，并且上限为O(n)。这是因为想要的总和要么包含在中位数以上的一半中，要么我们需要从下半部分添加更多内容，在这种情况下，我们不需要检查上半部分。"最初的回答"

- גלעד ברקן

---

@RobertBaron 选择算法可以产生分区作为副产品。 - גלעד ברקן

@RobertBaron Robert，我们只需要查看每个分区的一部分。我们先迭代N，然后是N/2，然后是N/4等等，直到我们得到一个解决方案。这个总和收敛于2N。怎么了？ - גלעד ברקן

@RobertBaron 你是怎么得到O(n log n)的？我得到的是n + n/2 + n/4 + n/8... 这个收敛于2n。顺便说一下，这里有一个线性时间复杂度的中位数查找算法：https://rcoh.me/posts/linear-time-median-finding/ - גלעד ברקן

@RobertBaron 这里有另一个很好的参考资料：https://dev59.com/jmgv5IYBdhLWcg3wW_h_。（我仍在等待您解释如何得出总体O（n log n）假设O（n）中位数选择。） - גלעד ברקן

我认为这是正确的方法。如果我有最终解决方案，我会发布更新。感谢大家的贡献！ - MadMat

Answer 2

你可以将值舍入到3个小数位，并使用桶排序。使用3个小数位，您将需要1000个桶。根据您的问题，您可以使用更多或更少的桶。时间复杂度将为O(n + k)，其中k是桶的数量。

在您的桶中，您可以存储精确值，因此在扫描桶以获取所需总和时，您将使用实际值。您说前几个值通常代表所有值的1％。那么顶部的桶应该只包含很少的值。

- RobertBaron

---

嗨，罗伯特，希望你一切都好。感谢你的贡献。我认为快速选择的想法最相关。一旦最终解决方案出现，我会进行更新。 - MadMat