给定的阵列（让我们假设非负整数），我们需要找到最小长度的子集，使得元件的总和是不大于K. K时是作为输入提供另一个整数。

Given an array (lets assume of non negative integers) we are required to find the smallest length subset such that sum of elements is no less than K. K is another integer provided as input.

有没有可能有时间复杂度为O（n）溶液[大的n OH]？

Is it possible to have a solution with time complexity O(n) [big oh of n]?

我目前的想法是大致如下： 我们可以排序澳阵列（N * log n）的，然后遍历数组排序，从人数最多的启动和维持运行总和，直到运行总和为> = K。

my current thinking is along the following lines: we could sort the array in O(n * log n) and then iterate over the sorted array starting from the largest number and maintaining the running sum until the running sum becomes >= K.

然而，这将在运行的O时间最坏情况下（N *（日志的n + 1））。

However, this would have worst case running time of O(n * (log n + 1)).

因此​​，如果任何人都可以共享为O这样做（n）时间的想法，我真的AP preciate ..

So if anyone could share ideas of doing this in O(n) time, I would really appreciate..

注：子阵列的元件不必须是原始阵列的连续序列在这方面

Note: The elements of subarray dont have to be a contiguous sequence of the original array in this context

推荐答案

有一个线性时间算法寻找K个最大的数字 - 的 http://en.wikipedia.org/wiki/Selection_algorithm 。当然，你要的只是足够大的数字来概括至少为K的东西。

There is a linear time algorithm for finding the K largest numbers - http://en.wikipedia.org/wiki/Selection_algorithm. Of course what you want is just enough largest numbers to sum up to at least K.

在标准的选择算法，采取随机支点，再看看，看看有多少数字落在它的每一面。然后，您可以选择接受或拒绝的一半，并保持工作的另一半。刚才看着在每半个每个数字，依次 - 每个枢轴阶段的成本是线性的，但认为在各阶段的数据量减少了足够迅速，总成本仍然只有线性

In the standard selection algorithm, you take a random pivot and then look to see how many numbers fall on each side of it. You then either accept or reject one half, and keep working on the other half. You have just looked at each number in each half, in turn - the cost of each pivot stage is linear, but the amount of data considered at each stage reduces fast enough that the total cost is still only linear.

枢轴阶段的成本仍将如果你把枢轴上述所有数字之和只能是线性的。利用这一点，你可以推断出，如果接受所有这些数字，加上previously选择任何号码，会给你加起来至少K.如果是这样，你能够摆脱对方号码和使用号码的集合枢轴为下通上面的数字。如果没有，你能接受的支点上面的所有号码，并使用支点下方的数字为下传。由于与选择算法，枢轴本身任何关系给你一些特殊情况和早期找到一个确切的答案的可能性。

The cost of a pivot stage will still be only linear if you take the sum of all the numbers above the pivot. Using this, you can work out if accepting all these numbers, together with any numbers previously selected, would give you a collection of numbers that add up to at least K. If it does, you can ditch the other numbers and use the numbers above the pivot for the next pass. If it does not, you can accept all the numbers above the pivot, and use the numbers below the pivot for the next pass. As with the selection algorithm, the pivot itself and any ties give you a few special cases and the possibility of finding an exact answer early.

（所以我觉得你可以在（随机）线性时间使用，而不是有多少数字是枢轴上面，你看支点上述数字的总和选择算法的修改版本，做到这一点。

(So I think you can do this in (randomized) linear time using a modified version of the selection algorithm in which you look at the sum of the numbers above the pivot, instead of how many numbers are above the pivot.