N 個の整数を含む大きな配列があるとします。
const unsigned N = 1e12;
int array[N] = { 1, 3 , 8, -5, 4, 3, -1 -6, 6, ....., N};
さまざまな指標の範囲内で最小の要素を何度も照会する必要がありますi j。最小値を返す複雑さは、O(ji) よりも小さくする必要があり、問題は O(N^2) 未満のメモリを使用して解決する必要があります。
これはどのように行うことができますか？
質問する
375 次
4 に答える
3
RMQは次のように機能します。
配列M[N][logN]を保持します。ここで、M [i] [j]は、iから始まり、長さが2^jの範囲の最小数を示します。その配列を埋めるために、最初にすべてのM [i] [0]値を計算します。これらはすべて、M [i] [0] = A [i]に等しくなります（A [i]は元の配列です）。その後、誘導により、各M [i] [j]はmin（M [i] [j-1]、M [i +（1 <<（j-1））] [j-1]）に等しくなります。つまり、左と右の部分を最小限に抑えることで、より長い間隔の値を取得します。これは、最短から最長の間隔に進むときに、前の手順で計算する必要があります。
その後、[a..b]間隔で最小値を取得するには、2^Pが間隔[a..b]の長さを超えないように最大のPを見つける必要があります。そして答えはmin（M [a] [P]、M [b-（1 << P）+ 1] [P]）になります
于 2013-03-08T10:40:17.953 に答える
2
静的配列の場合、前述のように、最速のソリューションは O(1) with O(n) preproc です。しかし、実際には、次のアプローチのいずれかを使用することをお勧めします。これは、動的配列でも機能し、理解しやすく、コーディングしやすいように思えます。
- 配列をそれぞれ sqrt(n) 要素を持つ sqrt(n) セクションに分割し、それらの各セグメントの最小値を格納します。各 (i,j) には、これらのセグメントの一部と、左右の要素が含まれる場合があります。これらの要素と保存されているセグメントの回答を渡して、最小値を見つけます。これには、O(n) プリプロシージャ、O(sqrt(n)) クエリ、O(sqrt(n)) 更新、および O(sqrt(n)) メモリが必要です。コーディングも非常に簡単です。
- アレイ上に最小セグメント ツリーを構築します。これにより、クエリ/更新に O(logn)、メモリ/プリプロシージャに O(n) が与えられます。
于 2013-03-08T11:49:48.493 に答える
1
ロシア語を知っている人には、これが解決策です: http://e-maxx.ru/algo/rmq ロシア語を知らない人のために、申し訳ありませんが、私は何かを見つけていません。誰かが見つけたら、私の答えを編集してください。
于 2013-03-08T10:37:50.837 に答える
1
簡単な解決策は、エントリ [i, j] が範囲 arr[i..j] の最小値を格納する 2D 配列を作成することです。特定の範囲の最小値を O(1) 時間で計算できるようになりましたが、前処理には O(n^2) 時間がかかります。また、このアプローチには O(n^2) 余分なスペースが必要であり、大きな入力配列では巨大になる可能性があります。
もう 1 つの解決策は、セグメント ツリーを構築することです。セグメント ツリーを使用して、前処理とクエリを適度な時間で行うことができます。セグメント ツリーでは、前処理時間は O(n) で、範囲最小クエリの時間は O(Logn) です。必要な余分なスペースは、セグメント ツリーを格納するために O(n) です。
セグメント ツリーの表現
- リーフ ノードは、入力配列の要素です。
- 各内部ノードは、その下にあるすべてのリーフの最小値を表します。
セグメント ツリーの構築については、ここで詳しく説明します。
http://www.geeksforgeeks.org/segment-tree-set-1-range-minimum-query/
于 2013-03-08T10:41:27.220 に答える