16

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

有没有改善nlog(n)。

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

4

5 回答 5

9

这是一个算法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 时。

于 2011-05-11T15:01:40.097 回答
7

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

因为值的范围是有限的，所以您可以使用非比较排序算法，例如 鸽巢排序或基数排序。n lg(n)

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

于 2011-05-11T12:18:22.610 回答
6

这是该问题的 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)
于 2011-05-12T03:06:28.480 回答
5

您可以对 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)。

于 2011-05-11T14:51:21.010 回答
0
  1. 消除数字< S，如果找到某个数字==S，则解决
  2. 鸽子洞排序数字 < S

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

于 2011-05-15T05:19:53.363 回答