arrays - 总和至少为 K 的最小数字集

Question

给定一个包含 n 个对象的列表，编写一个函数，输出总和至少为 K 的最小数字集。 跟进：你能击败 O(n ln n) 吗？

最小集合将是具有 1 个元素的集合。难道我们只需要遍历数组并找到一个元素，即> = K。

否则对于 O(nlgn)，我知道我们必须首先对数组进行排序，然后我们才能找到总和 >=k 的对或三元组。如果我们没有找到这样的组合并且必须使用更大的集合怎么办，这个问题会不会与 N sum 问题相同？

Answer 1

这与 N Sum 问题非常不同，因为它要求集合加起来至少为K，而不是恰好为 K。

它可以在 O(n ln n) 内完成，方法是对列表进行排序并从最大元素开始直到总和大于 K。可以通过首先扫描列表来优化它，以消除单个数字 > K 和在所有成员的总和 < K 的情况下。您还可以获得列表的平均值，并且有时只对列表的“上”半部分进行排序。但是，这些优化并没有改善 O(n ln n) 时间。

排序可以使用索引数组（或整数列表）来完成，因此不需要移动原始值或对象。

Answer 2

这是一个使用线性时间中值查找作为子程序的线性算法：

Findsum(A, K) {
  Let n be the length of A.
  Let M be the median element of A, found in linear time.
  Let L be the elements of A less than M.
  Let U be the elements of A greater than M.
  Let E be the elements of A equal to M.
  If the sum of the elements in U is at least K,
    Return Findsum(U, K).
  Else, if the sum of the elements in U and E is at least K,
    Return U together with enough elements of E that the sum is at least K.
  Else,
    Return Findsum(L, K - sum(U) - sum(E)).
}

每个递归调用最多在一个大小为 A 一半的列表上完成，所有其他步骤最多花费线性时间，因此该算法总体上花费线性时间。