algorithm - 在一组实数中查找第 k 个元素子集(《编程珠玑》一书)

Question

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

“给定一个由 n 个实数、一个实数 t 和一个整数 k 组成的集合，你能多快确定是否存在该集合的 k 个元素子集，其总和最多为 t？”

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

解决方案是否正确？

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

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

Answer 1

因为您只需要根据您的问题对前 k 个元素进行排序，所以我建议如下:-

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

2. 对数组前k个元素求和，判断是否小于t

时间复杂度 O(N + k) = O(N) 因为 k 是 O(N)

Randomized Selection

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