4

N個の整数の配列を考えてみましょう。その要素の平均が与えられた数kよりも大きくなる（または等しくなる）ように、最も長い連続するサブ配列を見つけます。

明白な答えはO（n ^ 2）の複雑さを持っています。もっと上手くできますか？

4

2 に答える 2

10

O（n）時間のすべての値からkを引くことにより、この問題を合計>=0の最長の連続サブアレイに減らすことができます。次に、プレフィックスの合計を計算しましょう。

index    0     1     2     3     4     5     6
array          2     -3    3     2     0     -1
prefix   0     2     -1    2     5     5     4

現在、この問題は、で最も離れている2つのインデックスを見つけることprefix_right - prefix_left >= 0です。新しいプレフィックスインデックス配列を作成し、プレフィックス、インデックスの順に並べ替えてみましょう。

index    2     0     1     3     6     4     5
prefix   -1    0     2     2     4     5     5

次に、右から左へのスイープを実行して、プレフィックスごとに、現在のプレフィックス以上のプレフィックスを持つ最大インデックスを計算できます。

index    2     0     1     3     6     4     5
prefix   -1    0     2     2     4     5     5
maxind   6     6     6     6     6     5     5

それでは、元のプレフィックス配列に戻りましょう。プレフィックスとインデックスのペアごとに、新しい配列でバイナリ検索を実行して、最小のプレフィックス>=現在のプレフィックスを見つけます。バイナリ検索されたプレフィックスのmaxindから、現在のプレフィックスのインデックスを減算して、現在のインデックスから始まる可能な限り最良のシーケンス長を取得します。最大長のシーケンスを取ります。

このアルゴリズムは、ソートとn個の二分探索のためにO（n log n）です。

于 2012-11-20T16:25:50.233 に答える
1

O（n）時間とO（n）空間の複雑さの問題を解決できます：
私は素朴で最適なアプローチで試しました。
つまり、問題には2つのステップが含まれます。
（1）各ar [i]からkを減算し、新しい配列で累積値を見つけます。新しい配列をcumArr[]と呼びましょう。
（2）ここで、問題は、j>iおよびcumArr[j]> cumArr[i]となるようにCumArr[]でmax（j-1）を見つけることになります。このステップは有名な質問であり、多くの場所で見つけることができます。

実行中のコードの詳細は次のとおりです：http： //codeshare.io/Y1Xc8

扱いやすい小さなコーナーケースがあるかもしれません。
友達の考えを教えてください。

于 2015-09-01T02:45:21.493 に答える