7

配列（非負の整数を想定）が与えられた場合、要素の合計がK以上になるような最小の長さのサブセットを見つける必要があります。Kは入力として提供される別の整数です。

時間計算量O（n）[big oh of n]の解を得ることができますか？

私の現在の考え方は次のとおりです。配列をO（n * log n）で並べ替えてから、並べ替えられた配列を最大数から繰り返し、現在の合計が>=Kになるまで現在の合計を維持することができます。

ただし、これは最悪の場合の実行時間O（n *（log n + 1））になります。

ですから、誰かがO（n）時間でこれを行うというアイデアを共有できれば、私は本当に感謝します。

注：このコンテキストでは、サブ配列の要素は元の配列の連続したシーケンスである必要はありません

4

6 に答える 6

7

K 個の最大数を見つけるための線形時間アルゴリズムがあります - http://en.wikipedia.org/wiki/Selection_algorithm。もちろん、あなたが望むのは、合計が少なくとも K になるのに十分な最大数です。

標準の選択アルゴリズムでは、ランダムなピボットを取り、その両側にいくつの数字が収まるかを調べます。次に、半分を受け入れるか拒否し、残りの半分に取り組み続けます。各半分の各数値を順番に見てきました。各ピボット ステージのコストは線形ですが、各ステージで考慮されるデータの量は急速に減少するため、総コストは依然として線形にすぎません。

ピボット ステージのコストは、ピボットより上にあるすべての数値の合計をとった場合でも線形になります。これを使用して、これらすべての数値を、以前に選択した数値と一緒に受け入れると、合計で少なくとも K になる数値のコレクションが得られるかどうかを判断できます。そうであれば、他の数値を捨てて上記の数値を使用できます。次のパスのピボット。そうでない場合は、ピボットより上にあるすべての数値を受け入れて、ピボットより下にある数値を次のパスに使用できます。選択アルゴリズムと同様に、ピボット自体と任意の同点によって、いくつかの特殊なケースと正確な答えを早期に見つける可能性が与えられます。

(したがって、ピボットの上にいくつの数字があるかではなく、ピボットの上にある数字の合計を見る選択アルゴリズムの修正版を使用して、(ランダム化された) 線形時間でこれを行うことができると思います。

于 2012-10-23T04:23:44.260 に答える
5

これは動的計画法の問題のようです。配列を構築するときは、特定の各インデックスまでの累積合計を含む別の配列を構築します。したがってi、その配列のそれぞれには からの合計があり1..iます。

p..qこれで、インデックスの値の合計が であることが簡単にわかりますSUM(q) - SUM(p-1)(特別な場合はSUM(0)です0)。明らかに、ここでは 1 ベースのインデックスを使用しています... この操作は O(1) なので、最適なものを見つけるには O(n) アルゴリズムが必要です。

p簡単な解決策は、 andを追跡し、qこれらを配列内で処理することです。最初に展開しqます。次に、毛虫がアレイを這うように、収縮pと拡張を繰り返します。q

展開するにはq:

p <- 1
q <- 1

while SUM(q) - SUM(p-1) < K
    q <- q + 1
end while

現在qは、部分配列の合計がちょうど超えた (または等しい) 位置にありKます。サブ配列の長さは ですq - p + 1。

ループの後、q部分配列の長さが現在のベストよりも短いかどうかをテストします。次にp、(最適なソリューションを誤ってスキップしないように) 1 ステップ進み、もう一度進みます。

配列を実際に作成する必要はありませんSUM...サブ配列の合計を作成するだけで済みます...直前のものではなく、「実際の」を使用することに戻る必要がありますp。

subsum <- VAL(1)
p <- 1
q <- 1

while q <= N
    -- Expand
    while q < N and subsum < K
        q <- q + 1
        subsum <- subsum + VAL(q)
    end while

    -- Check the length against our current best
    len <- q - p + 1
    if len < bestlen
        ...
    end if

    -- Contract
    subsum <- subsum - VAL(p)
    p <- p + 1
end while

ノート：

j_random_hacker は次のように述べています: O(n^2) の可能なすべての個別のサブ配列ではなく、このアルゴリズムが検査する O(n) の個別のサブ配列のみを検査することが許容される理由を正確に説明するのに役立ちます。

動的プログラミングの哲学は次のとおりです。

  1. 最適でない結果につながるソリューション パスをたどらないでください。と
  2. 以前の解の知識を使用して、新しい解を計算します。

この場合、単一の解候補 ( の(p,q)ようなものp <= q) は、要素の合計によって計算されます。これらの要素は正の整数であるため、任意の解候補(p,q)について、解候補(p,q+1)が大きくなることがわかっています。

(p,q)したがって、 が最小解である場合はそうではないことがわかり(p,q+1)ます。候補が見つかったらすぐに検索を終了し、その候補がこれまでに見たどの候補よりも優れているかどうかをテストします。つまり、各 に対してp、1 つの候補のみをテストする必要があります。これにより、両方が増加するだけpでqなく、常に増加するため、検索は線形になります。

これの他の部分 (以前のソリューションを使用) はsum(p,q+1) = sum(p,q) + X(q+1)、それと同様に認識することから来ていsum(p+1,q) = sum(p,q) - X(p)ます。pしたがって、すべてのステップの間およびすべてのステップですべての要素を合計する必要はありませんq。検索ポインターの 1 つを進めるたびに、1 つの値を加算または減算するだけで済みます。

それが役立つことを願っています。

于 2012-10-23T04:15:24.470 に答える
3

OPは、コメントに対する彼の回答で、問題はサブセットを見つけることであり、必ずしも連続したシーケンスではないことを明らかにしました（「サブアレイ」という用語は明らかに貧弱でした）。次に、マクドウェラが示した方法は正しいと思います。次の手順で構成されます。

N 個の要素から始めて、MEDIAN 要素を見つけます (つまり、(N/2) 番目の要素で、あなたが持っておらず、構築もしていない、ソートされた配列を想像してください)。これは、O(n) であることが証明された「Median of Medians」アルゴリズムで達成されます。すでに与えられ、ここで繰り返されている wiki ref を参照してください:選択アルゴリズム。Median of Median アルゴリズムのセクションを参照してください。

中央値の要素を持つ: 完全なセットを線形にスキャンし、「下」と「上」に分割し、その間、「半分」のそれぞれについて、追跡したいことを合計、カウント、および実行します。このステップは（また）O（N）です。

スキャンが完了し、「上半分」の合計がターゲット (K) を上回っている場合、下半分のことはすべて忘れて、サイズが (おおよそ) N/2 である上半分について手順を繰り返します。一方、「上半分」の合計が K より小さい場合は、その上半分を最終結果に追加し、その合計を K から引き、下半分で手順を繰り返します。

全体として、サイズ N、N/2、N/4、N/8 などのセットを、それぞれのサイズ M に関して O(M) で処理します。したがって、全体的なものも N で線形になります。なぜなら、N + N/2 + N/4 + N/8 ... 2N 未満のままです。

于 2012-10-23T09:15:19.463 に答える
1

これは、十分に高速なソリューションです。ほぼ一直線だと思います。

def solve(A, k):
    assert sum(A) >= k
    max_ = max(A)
    min_ = min(A)
    n = len(A)
    if sum(A) - min_ < k:
        return A
    bucket_size = (max_ - min_)/n + 1
    buckets = []
    for i in range(n):
        buckets.append([])
    for item in A:
        bucket = (item - min_)/bucket_size
        buckets[bucket].append(item)

    solution = []

    while True:
        bucket = buckets.pop() #the last bucket
        sum_ = sum(bucket)
        if sum_ >= k:
            #don't need everything from this bucket
            return solution + solve(bucket, k)
        else:
            k -= sum_
            solution += bucket

print solve([5,2,7,52,30,12,18], 100)
"[52, 30, 18]"
于 2012-10-23T05:16:22.660 に答える
0

サブ配列は、配列の定義によって連続している必要があります。

2 つのポインター (開始、終了) を使用します。それらを配列の先頭に初期化します。(start, end) 間の現在の合計を追跡し、end を 1 つずつ右に移動します。終了ポインタを移動するたびに、sum = sum + array[end] になります。

そして、sum >= target の場合、start を右に移動し始め、sum = sum - array[start] として sum を追跡し続けます。

開始を右に移動しながら、合計が目標を下回っていないことを確認し続けます。また、length = end - start + 1 と minLength = min(minLength, length) を実行して、長さを追跡する必要もあります。

両方のポインターをできるだけ右に移動したら、minLength を返すだけです。

一般的な考え方は、最初に条件 (合計 >= ターゲット) を満たす「ウィンドウ」を見つけ、次にウィンドウを一度に 1 要素ずつ右にスライドさせ、ウィンドウを移動するたびにウィンドウ サイズを最小に保つことです。

于 2013-10-16T04:09:18.620 に答える
0

「サブ配列」という用語は、配列の連続した部分を意味すると思います（hereのように、例として別の問題）。

したがって、最小長の部分配列を見つけるための単純な O(n) アルゴリズムがあります。

最初の要素に 2 つのインデックス (左、右) を設定し、配列の最後まで移動します。これらのインデックス間の合計をチェックし、合計が小さすぎる (またはポインターが等しい) 場合は右ポインターを進め、合計が大きい場合は左に進めます。

于 2012-10-23T05:17:32.197 に答える