我有一个练习要求:
- 考虑一个具有 n 个正整数和一个整数 k 的向量 T。提出一种算法,从 T 中选择最大数量的元素,使得所选元素的总和小于或等于 k。
我所做的是:
def findSumCount(L, k):
L.sort()
totalSum = L[0]
count = 1
for i in range(1, len(L), 1):
if(totalSum + L[i] <= k):
count = count + 1
totalSum = totalSum + L[i]
if(totalSum + L[i] > k): break
return count
findSumCount([1, 2, 3, 4], 5)
我认为当我对条目上的数组进行排序时,这是有效的(如果您认为它不起作用,请给我一个反例)。但是,如果我之前没有排序(即在没有事先排序的情况下迭代数组),我就看不到前进的道路。有任何想法吗?
获取总和低于某个值的尽可能多的元素
k
意味着您希望始终选择具有最低值的元素。因此,对输入数组进行排序,然后按升序排列元素,直到k
超出限制是您能做的最好的事情。复杂度低于 O(n logn + n) ~ O(n logn),其中 n 是 T 的大小。您为排序所付出的成本:)。如果您不想通过排序来改变输入列表,则始终可以获得与输入列表不同的排序列表。为此,您只需将初始语句替换为
L = sorted(L)
. 现在L
持有的列表与最初的列表不同。如果
k
相对较小,即要求和的元素数量相对于列表的大小相对较小,那么不对列表进行排序,而是从中构建堆可能会更有效。然后从中提取最小值,直到得到计数:复制列表(可选)和堆化列表的时间复杂度为 O(𝑛)。每次从堆中弹出的时间复杂度为 O(log𝑛),其中 𝑛 是当时堆的大小。因此,如果我们只需从堆中弹出 𝑚 个元素,时间复杂度为 O(𝑛 + 𝑚log𝑛)。
在最坏的情况下,如果所有元素都必须从列表中弹出,时间复杂度将为 O(𝑛log𝑛)。在这种情况下,它的时间复杂度与您提供的原始代码相同,但开销更大,因此实际上会更慢。
对您的代码进行备注
您的实施有几个问题:
如果列表中的所有元素都大于
k
,则不会返回正确答案,在这种情况下返回的计数应为 0。if(totalSum + L[i] > k)
当它已经执行了前面的块时,它也会评估表达式if
,其中L[i]
已经添加到totalSum
:这有点奇怪。它不会导致错误的结果,因为列表已排序,但最好将第二个转换if
为else
,甚至更好:反转第一个的条件if
并返回那里的计数。您至少可以节省执行添加的次数。由于
count
确实对应于排序列表中当前迭代值的索引,因此您可以将其设为循环变量。同时您可以通过 获取值enumerate
。考虑到这些评论,可能是:
如前所述,完全有可能在不进行排序的情况下解决这个问题,甚至通过结合二分搜索来解决很多辅助空间。此问题依赖于以下属性(已被识别):
最好先将较小的元素放入数组中,然后再将较大的元素放入数组中,因为较小的元素对总和的贡献较小,并且我们希望选取尽可能多的元素,同时将所选元素的总和保持在以下
k
。扭曲这个想法,我们可以通过找到最大的元素来最大化选择的元素数量,
limit
其中我们选择所有小于或等于 的元素limit
。一种查找方法limit
是测试数组中的每个值,但实际上我们可以通过仅选择某些候选值来limit
使用二分搜索来做得更好,因为我们只是想最大化limit
并可以立即快速丢弃太小/太大的候选值。完整的代码如下,是
findSumCountBsearch
这个想法的实现;它要求helper
评估候选人是否按照提议的方式工作limit
。还有一种边缘情况,limit
可以安全地包含所有小于 的元素,但实际上只能选择所有实例的子集limit
,这可以通过一些数学来处理。