1

这是来自编程珍珠版。2，第 2 栏，第 8 题：

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

一个简单的解决方案是对前 k 个元素进行排序和求和，这是我们找到这样一个和的最大希望。然而，在解决方案部分，Bentley 提到了一个需要 nlog(k) 时间的解决方案，尽管他没有给出如何找到它的提示。我一直在为此苦苦挣扎；我的一个想法是遍历列表并添加小于 t/k 的所有元素（在 O(n) 时间内）；假设有 m1 < k 这样的元素，它们的总和为 s1 < t。然后我们需要 k - m1 个元素，因此我们可以在 O(n) 时间内再次扫描列表，查找小于 (t - s1)/(k - m1) 的所有元素。再次添加，得到 s2 和 m2，然后如果 m2 < k，则再次查找小于 (t - s2)/(k - m2) 的所有元素。所以：

def kSubsetSumUnderT(inList, k, t):
    outList = []
    s = 0
    m = 0
    while len(outList) < k:
        toJoin = [i for i in inList where i < (t - s)/(k - m)]
        if len(toJoin):
            if len(toJoin) >= k - m:
                toJoin.sort()
                if(s + sum(toJoin[0:(k - m - 1)]) < t:
                    return True
                return False
            outList = outList + toJoin
            s += sum(toJoin)
            m += len(toJoin)
        else:
            return False

我的直觉是这可能是 O(nlog(k)) 算法，但我很难向自己证明。想法？

4

2 回答 2

2

考虑 t>0 和 的示例all([x>t for x in inList])。toJoin将永远是空的，你的算法甚至没有完成，更不用说在 O(nlog(k)) 中了。

您可能缺少的提示是http://en.wikipedia.org/wiki/Heap_(data_structure)

于 2014-08-22T20:59:32.917 回答
0

可能具有运行时间 Theta(n log k) 的自然算法是初始化一个具有 k 无穷大的最大堆，然后遍历数组，推送新元素并弹出最大值以在最后将 k 留在堆中。（正如 Bentley 所提到的，在 Theta(n) 时间，选择渐近更快。在实践中选择的最佳方法可能是堆积并弹出 min k 次，即 Theta(n + k log n) = Theta(n)当 k = O(n/log n) 时。）

于 2014-08-23T01:53:31.097 回答