3

n 個のオブジェクトのリストが与えられた場合、合計が少なくとも K になる数値の最小セットを出力する関数を作成します。フォロー アップ: O(n ln n) に勝てますか?

最小セットは 1 要素のセットになります。配列をトラバースして要素、つまり>= Kを見つける必要があるだけではありませんか.

それ以外の場合、O(nlgn) の場合、最初に配列をソートする必要があることを理解しています。次に、合計が >=k であるペアまたはトリプレットを見つけることができます。そのような組み合わせが見つからず、より大きなセットに行かなければならない場合、この問題は N サムの問題と同じではありませんか?

4

2 に答える 2

4

これは、正確に K ではなく、少なくともKまでセットを追加する必要があるため、N Sum 問題とは大きく異なります。

O(n ln n) でリストをソートし、合計が K よりも大きくなるまで最大要素から処理を進めることで実行できます。最初にリストをスキャンして、単一の数値 > K であり、すべてのメンバーの合計 < K の場合。リストの平均値を取得することもできます。場合によっては、リストの「上」半分だけをソートすることもできます。ただし、これらの最適化によって O(n ln n) 時間は改善されません。

並べ替えはインデックス配列 (または整数のリスト) を使用して実行できるため、元の値またはオブジェクトを移動する必要はありません。

于 2013-01-21T02:40:03.883 に答える
4

サブルーチンとして線形時間中央値検出を使用する線形アルゴリズムを次に示します。

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 の半分のサイズのリストで実行され、他のすべてのステップは最大で線形時間かかるため、このアルゴリズムは全体的に線形時間かかります。

于 2013-01-21T02:49:55.130 に答える