我正在解决Programming Pearls专栏2的问题。我遇到了这个问题：
“给出n个实数，一个实数t和一个整数k的集合，您能多快确定是否存在集合中最多包含t的k个元素子集？”
我的解决方案是对实数集进行排序，然后查看前k个元素的总和。如果该总和小于或等于t，则我们知道至少存在一组满足条件的集合。
解决方案正确吗？
有更好的解决方案吗？
注意：只是为了清楚起见，不要假设输入已经排序。
因为您只需要根据问题对前k个元素进行排序，所以我建议：-
使用随机选择O（N）选择数组中的第k个元素
取数组中前k个元素的和，并检查其是否小于t
时间复杂度 O(N + k) = O(N) as k is O(N)
注意：-当k与N相比很小时，最大堆可能会非常有效，因为存储的成本并不高，并且可以解决最坏情况O（Nlogk）的问题。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句