5

シーケンス が与えられた場合、 がシーケンス内の最初の要素である要素a[1], a[2], a[3] .... a[n]を ごとに検索する必要があります。a[i]a[j]a[j]a[i - 1], a[i - 2], a[i - 3]....a[j] < a[i]

言い換えれば、a[j]どこでa[j] < a[i]とを見つけなければなりません1<=j<i。しかし、そのような要素が複数ある場合は、最も近いものを選択する必要がありますa[i]。

たとえば、次の順序で:

2 6 5 8

6 と 5 の両方に 2 を出力し、8 に 5 を出力する必要があります。

これは で簡単に実行できることはわかっていますがO(n^2)、これを行うより効率的な方法はありますか?

4

1 に答える 1

3

stackO(n)を使用して実行できます。

a = your array
d = a stack
d.push(a[1])
for i = 2 to n do
  while d.top > a[i] do
    d.pop()

  print d.top if it exists, else -1
  d.push(a[i])

基本的に、dソートを維持し、最後の要素が常に より小さいことを確認しa[i]ます。このように、最後の要素dは常に探しているものになります。

ネストされたループのため、線形の複雑さはすぐにはわからないかもしれませんが、各要素がスタックを出て入るのは多くても 1 回であり、その回数は一定であることに注意してください。

于 2013-02-15T10:45:40.770 に答える