更新时间:2023-02-10 21:32:49
O(n + size(最小子集)* log(n))
的算法。如果最小子集远小于数组,则将为 O(n)
。
Here is an algorithm that is O(n + size(smallest subset) * log(n))
. If the smallest subset is much smaller than the array, this will be O(n)
.
读取 http://en.wikipedia.org/wiki/Heap_%28data_structure%29 该算法的描述不清楚(细节很浅,但是细节都在那里)。
Read http://en.wikipedia.org/wiki/Heap_%28data_structure%29 if my description of the algorithm is unclear (it is light on details, but the details are all there).
O(n)
可用。 O(大小(最小子集)* log(n))
。O(n)
.O(size(smallest subset) * log(n))
.这几乎可以肯定是他们所希望的答案,尽管没有得到应该不会破坏交易。
This is almost certainly the answer they were hoping for, though not getting it shouldn't be a deal breaker.
编辑:是另一个变体,通常变快,但变慢。
Here is another variant that is often faster, but can be slower.
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时。
If we get to reject most of the array without manipulating our heap, this can be up to twice as fast as the previous solution. But it is also possible to be slower, such as when the last element in the array happens to be bigger than S.