给定一个数组(假设非负整数),我们需要找到最小长度子集,使得元素之和不小于K.K是另一个作为输入提供的整数.
是否有可能得到时间复杂度为O(n)[n的大哦]的解决方案？
我目前的想法是以下几行:我们可以在O(n*log n)中对数组进行排序,然后从最大数字开始迭代排序数组并保持运行总和,直到运行总和变为> = K.
但是,这将具有O(n*(log n + 1))的最差情况运行时间.
所以如果有人能在O(n)时间分享这样做的想法,我真的很感激..
注意:在此上下文中,子数组的元素不必是原始数组的连续序列