找到最少的元素数量，使它们的总和等于或超过S。

Question

我知道可以通过对数组进行排序并取更大的数字，直到满足所需条件。 这将需要至少nlog(n)的排序时间。

是否有比nlog(n)更好的方法。

我们可以假设所有数字都为正数。

- Shamim Hafiz - MSFT

---

一种O(n log(n))的算法还不能让他们相信你是一个好的候选人吗？在我看来这个算法已经可以了。 - Simen S

@equality：S 不需要是常量，只需要是已知的。如果它是常量或有界的，你可以通过提前分配桶来提高实际性能，但这对算法的理论复杂度没有影响。 - verdesmarald

@equality：它是50而不是一个公式。我不确定问题是否被错误地描述为使您认为它是一个函数而不是一个常量值。 - Shamim Hafiz - MSFT

@equality: 当我说“已知”时，我指的是“在任何计算之前已知”。比较排序存在硬性的n lg(n)限制的原因是你事先不知道值域范围、数量等信息。而非比较排序在某些情况下表现更好的原因是它们能够提前获得一些信息。 - verdesmarald

我认为我的解决方案应该被接受。它可以给出最优的答案，而不需要任何快速整数排序或对输入进行任何假设。 - Rob Neuhaus

Answer 1

这是一个算法，时间复杂度为O(n + size(smallest subset) * log(n))。如果最小子集比数组小很多，则时间复杂度为O(n)。

如果我的算法描述不清楚，可以阅读http://en.wikipedia.org/wiki/Heap_%28data_structure%29（该页面详细介绍了堆的相关细节）。

具体步骤如下：

1. 将数组转换成堆，使得最大元素在O(n)的时间内可用。 2. 重复从堆中提取最大元素，直到它们的总和足够大。这需要O(size(smallest subset) * log(n))的时间。

这几乎肯定是他们期望的答案，但如果没有得到这个答案也不应该成为决定因素。

另外，这里还有一种变体，通常速度更快，但有时可能会更慢。

Walk through elements, until the sum of the first few exceeds S.  Store current_sum.
Copy those elements into an array.
Heapify that array such that the minimum is easy to find, remember the minimum.
For each remaining element in the main array:
    if min(in our heap) < element:
        insert element into heap
        increase current_sum by element
        while S + min(in our heap) < current_sum:
            current_sum -= min(in our heap)
            remove min from heap

如果我们能够在不操纵堆的情况下拒绝大部分数组，那么这种方法可以比之前的解决方案快两倍。但也有可能会更慢，例如当数组中最后一个元素恰好比S大时。

- btilly

---

这是O(n + K log n)（而不是你所声称的O(n + K log K)），对吧？虽然如此，还是要点个赞。这绝对是目前为止最好的答案。 - Aryabhatta

@Moron：哎呀，你说得对。我之前有一种方法可以到达下限，但意识到它通常会更差。稍后我会添加那个解决方案。 - btilly

@Moron：添加了第二个解决方案。 - btilly

+1，这是一个更好的解决方案。当涉及到堆时，我的功夫很弱；如果您已经知道所有元素，则构建它们可能是线性时间，谢谢！ - verdesmarald

Answer 2

假设这些数字是整数，您可以改进通常的n lg(n)排序复杂度，因为在这种情况下，我们有额外的信息，即值介于0和S之间（对于我们的目的，大于S的整数与S相同）。

由于值的范围是有限的，您可以使用非比较排序算法，如Pigeonhole Sort或Radix Sort，以降低到n lg(n)以下。

请注意，这些方法依赖于S的某些函数，因此如果S足够大（而n保持足够小），则最好恢复到比较排序。

- verdesmarald

---

我可能错了，但如果你做了类似鸽巢的东西，你实际上只需要执行排序的第一步（将数据放入巢穴），然后从数据的末尾添加直到达到 >= S，这样可以省去将元素重新排序的步骤。 - pstrjds

如果您使用固定大小的整数，那么您只能“知道”整数范围从0到S。如果您使用大整数，那么您将回到“n log n”。 - hammar

@veredesmarald：只有当_S_的大小固定时，该论点才有效。 - hammar

@hammar：很抱歉，我不明白你的意思。显然，对于足够大的S，比较排序的性能更好（正如我最初所说），但是S的编程表示与任何事情有什么关系呢？ - verdesmarald

换句话说：鸽巢法将为您提供一个O(n+S)的算法。在许多情况下，这比O(n log(n))更好，特别是如果S不比n大太多。 - Simen S

Answer 3

这里提供了一个期望时间复杂度为O(n)的解决方案。类似于Moron的想法，但我们不会在每一步中丢弃选择算法所做的工作，并且我们从中间的元素开始尝试，而不是使用重复加倍的方法。

或者说，这实际上仅仅是在快速选择中加入了一些额外的记录剩余总和的操作。

首先，很明显，如果你将元素按排序顺序排列，你只需要先选最大的元素，直到超过所需总和。我们的解决方案也是这样的，除了我们会尽力不去揭示排序信息，因为排序很慢。

你想要能够确定一个给定值是否是截止点。如果我们包括该值以及所有大于它的值，我们达到或超过S，但当我们移除它时，我们低于S，这时我们就成功了。

下面是伪代码，我没有测试过极端情况，但这可以让你理解思路。

def Solve(arr, s):
  # We could get rid of worse case O(n^2) behavior that basically never happens 
  # by selecting the median here deterministically, but in practice, the constant
  # factor on the algorithm will be much worse.
  p = random_element(arr)
  left_arr, right_arr = partition(arr, p)
  # assume p is in neither left_arr nor right_arr
  right_sum = sum(right_arr)
  if right_sum + p >= s:
    if right_sum < s:
      # solved it, p forms the cut off
      return len(right_arr) + 1    
    # took too much, at least we eliminated left_arr and p
    return Solve(right_arr, s) 
  else:
    # didn't take enough yet, include all elements from and eliminate right_arr and p
    return len(right_arr) + 1 + Solve(left_arr, s - right_sum - p)  

- Rob Neuhaus

---

+1 - 但是基于随机枢轴的分区算法（快速排序等）在枢轴始终不平衡时可能具有糟糕的最坏情况性能。我不确定这种情况下是O(n^2)还是O(n log n)。此外，重复求和（朴素实现）会破坏性能要求-您需要跟踪随着分区更改数组以及修改上限/下限来克服该问题而导致的总和如何随时间变化。 - user180247

是的，在最坏情况下，它的时间复杂度是O(n^2)。通过进行确定性中位数查找并围绕其进行枢轴选择，可以消除该因子并将其转换为O(n)的最坏情况，但这样的解决方案在实践中基本上总是会更慢（接受随机性！）。我改进了伪代码以不重新计算sum(right_arr)，但这对于渐近行为来说并不是必要的，只有常数因子。一旦我们消除了数组的一部分，我们就永远不需要计算它们的和，也不需要再次检查它们（当我们丢弃左侧时，我们永远不会取它们，当我们丢弃右侧时，我们会取所有它们）。 - Rob Neuhaus

好的，关于重新计算，我会相信你的 - 通常我的直觉猜测比我仔细计算更可靠，但遗憾的是，“更可靠”通常仍然相当不可靠。 - user180247

很好的回答。我比较喜欢这个。而且，即使在最坏情况下也可以将其变成O（n log（S）），而不会影响平均情况。我们有一个整数数组，范围有限。让每个其他轴心点位于该范围内整数的中点上，而不是数组中的值。这保证收敛于 O(log(S)) 步。（或者，您可以在最后三次选择没有足够减少搜索空间时进行确定性中位数查找。这使得复杂度为 O(n)，而在平均情况下不会影响性能。） - btilly

Answer 4

Theta(nlogn)的改进之一是使用O(n log K)的算法，其中K是所需的最小元素数量。

因此，如果K是常数或者说是log n，这比排序更好（渐近意义下）。当然，如果K是n^epsilon，那么这就不比Theta(n logn)更好了。

做法是使用选择算法，它可以在O(n)的时间内告诉你第i个最大的元素。

现在对K进行二分搜索，从i=1（最大值）开始，每次翻倍i等。

找到第i个最大值，找到前i个最大元素的和，并检查它是否大于S。

这样，您将运行O(log K)次选择算法（即O(n)），总运行时间为O(n log K)。

- Aryabhatta

---

我之前没有想到这个答案，因为我知道更快的标准解决方案。但这是一个聪明的回答。+1 - btilly

@btilly：仅在理论上 :-) 你的答案即使在实践中也是最好的。我想我知道标准解决方案，但我瞌睡的头脑一定以某种方式阻止了它！ - Aryabhatta

Answer 5

1. 删除小于S的数字，如果找到某个数字等于S，则问题解决
2. 将小于S的数字进行鸽巢排序

按照排序后从高到低的顺序求和元素，直到超过S。

- BiGYaN

---

请添加复杂度分析。谢谢。 - Shamim Hafiz - MSFT