2

サイズ1の A(0 indexed) という配列があります。

インデックス k1 (k1>=0) と A.size()-1 (つまり、最後の要素) の間の配列 A で最小値を見つけたいと考えています。

次に、配列の最後に値: (指定された範囲の最小要素 + いくつかの「ランダムな」定数) を挿入します。次に、インデックス k2 と A.size()-1 の間の最小値を見つけるための別のクエリがあります。最後に値 : (指定された範囲内の最小値 + 別の「ランダムな」定数) を挿入します。私はそのような多くのクエリを実行する必要があります。

たとえば、N 個のクエリがあるとします。単純なアプローチでは O(N^2) かかります。

配列が静的ではないため、セグメント ツリーを使用できません。しかし、賢明な方法は、サイズ N+1 配列のセグメント ツリーを作成することです。未知の値を無限大で埋めます。これにより、O(Nlog N) の複雑さが得られます。

NlogN の複雑さ、または N の他の方法はありますか?

4

1 に答える 1

3

ここでは、tree のような高度なデータ構造を使用する必要はまったくありません。単純なローカル変数とリストだけですべてを実行できます。

空のリストを作成します (たとえばminList)。

endインデックスから開始し、最初に指定されたstart配列のインデックスまで移動し、リストの先頭に最小値 ( からそのインデックスまで) を配置します (つまり、 do )。 endpush_front

提供された配列は次のとおりです。

70 10 50 40 60 90 20 30

したがって、結果minListは次のようになります。

10 10 20 20 20 20 20 30

それを行った後、継続的に変更する配列（たとえば、 ）に新しく追加された要素の中で最小のものを追跡するだけで済みます。minElemAppended

k = 5あなたが得るとしましょうrandomConstant= -10、そして

minElemAppended = minimum(minList[k-1] + randomConstant, minElemAppended)

このアプローチを採用することで、

  • 追加された部分、または最初に指定された配列をトラバースする必要はありません。
  • 要素をまったく追加しないオプションがあります。
  • 時間の複雑さ:クエリO(N)を処理します。N
  • スペースの複雑さ:O(N)格納するminList
于 2016-09-09T08:32:22.273 に答える