找到元素小于 S 的子集

Question

我必须找到解决以下问题的算法：

输入是两个自然数 S 和 k 以及一组未排序的 n 对不同数。

在 O(n) 中确定是否存在总计 <=S 的 k 个数字的子集。注意：k不应该是时间复杂度的一部分。

algorithm({x_1, ..., x_n}, k, S):
    if exists |{x_i, ..., x_j}| = k and x_i + ... x_j <= S return true

我找不到时间复杂度为 O(n) 的解决方案。

我能得到的是 O(kn)，因为我们搜索最小值的 k 倍，总和为：

algorithm(a={x_1, ..., x_n}, k, S):
    sum = 0
    for i=1,...,k:
        min = a.popFirst()
        for i=2,...,len(a):
            if(a[i] < min):
                t = a[i]
                a[i] = min
                min = t
        sum += min
    if sum <= S:
        return true
    else:
        return false

这是复杂度为 O(n) 且 return 正确的结果。我怎样才能松开k？

谢谢你的帮助，我真的很纠结这个！

Answer 1

您可以从该集合构建一个大小为 k 的最小堆。构建这个的时间复杂度是 O(n) 预期时间和 O(n log k) 最坏情况。堆应包含集合中的前 k 个最少元素。

那么直接可以看出堆中元素的总和为<= S。您不需要从堆中移除元素来计算总和。只需遍历堆计算总和即可。删除所有元素需要 k log k 复杂性。

你甚至不需要考虑下一个更高的元素，因为添加它们会导致总和大于 S

Answer 2

Quickselect 可用于查找 k 个最小元素：https://en.wikipedia.org/wiki/Quickselect

它基本上是快速排序，除了你只在主元有趣的一侧递归。

一个简单的实现在 O(N) 预期时间内运行，但使用中位数中位数 select一个枢轴，你可以使它成为一个真正的最坏情况界限：https://en.wikipedia.org/wiki/Median_of_medians

找到元素小于 S 的子集

find subset with elements smaller than S

algorithm

set

time-complexity

subset-sum