在一组实数中查找ak元素子集(Programming Pearls book)

Question

我正在解决Programming Pearls的Column2中的问题.我遇到了这个问题:

"给定一组n个实数,一个实数t和一个整数k,你能多快判断该组中是否存在一个总和最多t的k元素子集？"

我的解决方案是对实数组进行排序,然后查看前k个元素的总和.如果此总和小于或等于t,那么我们知道至少存在一个满足条件的集合.

解决方案是否正确？

是否有更好或不同的解决方案？

注意:为了清楚起见,不要假设输入已经排序.

Answer 1

因为你只需要根据你的问题排序的第一个k元素,我建议如下: -

1. 使用随机选择O(N)选择数组中的第k个元素

2. 获取数组中前k个元素的总和,并检查它是否小于t

时间复杂 O(N + k) = O(N) as k is O(N)

随机选择

注意: - 当k与N相比非常小时,那么最大堆可以非常高效,因为存储不会花费那么多,并且它可以解决最坏情况下的问题O(Nlogk).