总和至少为K的最小数字集-Java 学习之路

给定一个n个对象的列表，写一个函数，输出总和至少为K的最小数字集 . 跟随：你能打败O（n ln n）吗？

最小集合将是一个包含1个元素的集合 . 我们不必只是遍历数组并找到一个元素，即> = K.

否则对于O（nlgn），我知道我们必须首先对数组进行排序，然后我们可以找到总和> = k的对或三元组 . 如果我们找不到这样的组合并且必须选择更大的组合，那么这个问题与N和问题相同吗？

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

回复于 2024-05-06T03:29:06+08:00

4

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

它可以在O（n ln n）中通过对列表进行排序并从最大元素进行直到总和大于K来完成 . 可以通过首先扫描列表来优化，以消除单个数字> K的情况和所有成员之和<K的情况 . 您还可以获得列表的平均值，有时只对列表的“上半部分”进行排序 . 但是，这些优化不会改善O（n nn）时间 .

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

回复于 2024-05-06T03:29:06+08:00

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

2 回答

相关问题