1

例：

乱数のリストが与えられると[1,5,1,1,3,10,5,4,2,1]、テスト要素N=10 at index 5とMIN=20。

10aを含む最短のサブリストtotal>20は、明らかに[3,10,5,4]atotal=22とaを含むリストsize=4です。

問題：

そのようなサブリストを効率的に見つけるためのアルゴリズムは何ですか？

編集：

  1. 「最短」の条件を満たすさまざまなサブリストが存在する可能性があります。[10,5,4,2]と同じくらい短く[3,10,5,4]、有効な結果でもあります。

  2. この質問の「サブリスト」は、元のリストのアイテムの連続したブロックです。[5,10,5,4]は有効なサブリストではありません（代わりにサブセットと呼びます）。

4

2 に答える 2

1

次のアルゴリズムはO（n）である必要があります。

テスト要素から始めて、sum>=minになるまで要素を左側に追加します。これにより、サブリストの長さl（インデックスiから開始）の最初の推測が得られます。長さlのサブリストの開始インデックスiは、各ステップ（テスト要素に到達するまで）および各ステップテストで、最小より小さくなることなくサブリストを1つ短くする（右側、つまり長さlを減らす）ことができる場合は増加しません。

エッジケースに注意してください。左側の合計が十分に大きくないか、合計が十分に大きくありません。

于 2011-03-04T15:27:35.813 に答える
0

最短のサブリスト>MAXを見つけることは、最短のサブリスト<= MAXを見つけることと同じです。ここで、前または後ろの項目が追加された場合、サブリストの合計がMAX[1,5,1,1,3,10,5,4,2,1]をMAX=20超え[1,3,10]ます10。5の合計を与え19 < MAXます。最初の有効なサブリストはここにあります[5,1,1,3,10]。

アルゴリズム：

  1. marker見つかった最短のサブリストの長さのを作成します。
  2. カーソルleftとを作成しますright。
  3. 両方のカーソルをに設定しNます。
  4. left左while total(at left, ..., at N) <= MAXまたはに移動しleft = 0ます。
    1. left > 0に保存n - left + 1する場合marker。後藤6。
  5. right右while total(at left, ..., at right) <= MAXまたはに移動しright = list.size - 1ます。
    1. right < list.size - 1に保存right - left + 1する場合marker。
    2. それ以外の場合：戻りlist.sizeます。
  6. ループwhile left < N and right < list.size - 1：
    1. 右に1つずつ移動leftします。
    2. アイテムがある場合は、テストしますat right + 1。
      1. total + at right + 1 > MAXに保存right - left + 1する場合marker。
      2. それ以外の場合は、右に1つずつ右に移動します。

とにかく、ハワードに答えます。

于 2011-03-08T07:33:20.643 に答える