3

インタビュー中に以下の質問をされました（残念ながらN^2以上の答えは見つかりませんでした）

サイズ Nの指定された配列arrの場合、(インデックス内の) 各要素に対して、インデックス内の要素を返す必要があります(j > i)。つまり、 res[i] が arr[j を持つ配列 res を返す必要があります。 ],j>i,arr[j] > arr[i],j は、たとえば arr[k] > arr[i] となるように、すべてのインデックス k の中で最小です。unsigned intijarr[j] > arr[i]

arr[] = {3,1,4,2,5,7};
res[] = {2,2,4,4,5,-1};//-1 says no such index

より良い時間の複雑さでそれを行う提案はありますか? ありがとう

4

3 に答える 3

0

並列配列bを保持します。b[0]=0にします。aの要素を反復処理する実行を行います。進めながら、 bの値をaの連続するセルの差に設定します。

だから、もし

a[0]=9
a[1]=4
a[2]=17
a[3]=2
a[4]=3
a[5]=6
a[6]=0
a[7]=3
a[8]=1
a[9]=1
a[10]=7

それから、

b[0]=0
b[1]=-5
b[2]=13
b[3]=-15
b[4]=1
b[5]=3
b[6]=-6
b[7]=3
b[8]=-2
b[9]=0
b[10]=6

気にする必要があるのは、配列bの (-) セルだけです。ここで、配列bで逆方向に反復を開始します。たとえば、上記のb[10]から開始し ます。currentMax値を保持します。最初は配列の最初の最大値 (+) に設定されます。配列の末尾の (-) エントリについては何もできません。b[b.length]からb[0]まで逆方向に反復するときは、次のようにします。

currentMax を更新します。

currentMax += <value at the current cell of **b**>

if (currentMax<0) then /* elements-with-no-indexes*/ その後、正のb[i]エントリが見つかるまで続行し、見つかったら currentMaxの値をそれに設定します。

currentMaxの (+) 値は、currentMaxをリセットしたセルが、これまでにアクセスしたすべてのセルのインデックスであることを示し、(-) 値はインデックスのないセルであることを示します。

上記の例では、a[10] の7 はa[3]..a[9]内のすべてのインデックスです。なぜなら - currentMaxはセル 10 で初期化されたものである (その後リセットされない) -後のcurrentMaxの値これらすべての追加は、セル 4 までずっと (+) のままです (セル 4 は、セル 3 から 4 への変更を反映しています)。

b[3]で、currentMaxが 0 を下回ります。これは、セル 2 のインデックスがないことを意味します。b[2]で見つかった値は正ですが、currentMaxは負です。したがって、b[3] でcurrentMax=13を作成し、繰り返します。

配列サイズの線形 - O(n)時間かかります。

于 2013-11-06T06:52:32.050 に答える