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

Question

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

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

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

Answer 1

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

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 的一半，并且所有其他步骤最多花费线性时间，因此该算法总体上花费线性时间。