サブアレイのリストに対する質問

サイズNの配列Aが与えられた場合、Aのすべてのサブアレイを降順で含むリストを作成します。 2つのサブアレイBとCは、両方がサイズNになるまでゼロをパディングすることによって比較されます。次に、2つのサブアレイ要素を要素で比較し、差のポイントが観察されるとすぐに戻ります。与えられたxが上記の順序に従ってソートされたx番目の部分配列の最大要素を見つけなければならない場合、複数のクエリが与えられます。たとえば、配列Aが[3、1、2、4]の場合、次にソートサブアレイは次のようになりますサブアレイのリストに対する質問

[4]

[3、1、2、4]

[3、1、2]

[3,1]

[3]

[2,4]

[2]

[1、2、4] X = 3サブアレイ[3,1で最大の要素を見つけるに対応

[1,2]

[1]

クエリ2]。ここで答えは3になります。クエリの数が多く（10^5のオーダー）、配列内の要素の数も（10^5のオーダーで）大きくなる可能性があるため、 O（1）またはO（log N）またはO（sqrt N）時間内に各クエリに答えるためのいくつかの前処理を行います。私はこれを行う方法を把握していないようです。配列にユニークな要素が含まれているときに解決しましたが、配列に繰り返しが含まれている場合、どうすればこのことができますか？必要な情報を格納するのに役立つデータ構造はありますか？

出典

2016-12-04 Mahatma Gandhi

は、これらのサブリストの多くのがあるようになっていませんか？ – letmutx

各サブアレイの最大値を前処理段階の一部として保存するのはどうですか？ N番目（N + 1）/ 2個のサブアレイが存在するため、n番目のサブアレイへの到達はO（1）であり、事前計算がO（1） – danh

である場合は最大になります。 –

それは長さや累積数（接尾辞配列の先頭からの長さの合計）

だすべてのエントリストアの場合、この配列のためのバックオーダーでのビルドsuffix array（文字列のようにそれを考慮）

クエリのために必要見つけますcumul.countsとの累積数のバイナリ検索によってインデックス、そしてあなたの例については見つからサフィックス

の必要なプレフィックスを取得サフィックスが

4 (0) 
3124 (1) 
34 (5) 
124 (7)

です

クエリ3つの発見エントリ3124（1 < = 3 < 5）、及び（長さ）3-1=2-ndを取得する接頭辞は= 312

出典

2016-12-04 15:30:30 MBo

配列に繰り返しがある場合、これは機能しません。例えば、[4,2,5,4,3,2]と考える。 4で始まるサブアレイは、[4,3,2] [4,3,5,6,7,8,9,10,11,12,13,14] 5、4] [4,2,5] [4,2] [4] [4]（可読性の欠如して申し訳ありません） –

OK、問題があります。そしてまだそれを克服するための信頼できる方法はありません。一般的な接頭辞を考慮することは、2つの接尾辞に対して機能しますが、共通の接頭辞を持つ多くの接尾辞では複雑すぎます。 – MBo

私はいくつかのデータ構造を使って、接頭辞がすべての接尾辞で何度起こったかを計算し、その情報を使って部分配列を取得することを考えていました。しかし、それでもかなり複雑になります。 –

サブアレイのリストに対する質問

答えて

関連する問題