找到所需元素的最小数量,使其总和等于或超过S.

Question

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

是否有任何改善nlog(n).

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

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.

Answer 2

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

由于值的范围是有限的,您可以使用非比较排序算法,如 Pigeonhole Sort或Radix Sort,如下所示n lg(n).

请注意,这些方法取决于S的某些功能,因此如果S足够大(并且n保持足够小),您可能最好还原为比较排序.

Answer 3

您可以做的就是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).

Answer 4

这是问题的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)