1

問題は、長さの配列が与えられた場合、それらの要素がソートされたときに間隔1で等差数列を形成するように、長さNのすべてのサブシーケンスを見つける必要があることです。ソートすると、共通の差が1のAPが生成されるため、このようなサブシーケンスの1つと見なされます。WW[1,4,6,3,5,2,7,9]W[4,6,3,5,2][2,3,4,5,6]

頭に浮かぶ当面の解決策は、スライディングウィンドウを用意することです。新しい要素ごとに、古い要素をポップし、新しい要素をプッシュして、ウィンドウを並べ替えます。そのウィンドウの場合window[w-1] - window[0] + 1 = w、それはそのようなサブシーケンスです。ただし、時間がかかりますが、 CodechefO(NlogN)のソリューションでは、両端キューを使用する時間アルゴリズムが提案されています。アルゴリズム、何がプッシュおよびポップされるのか、なぜそうなるのか、そして新しい要素ごとに頼る必要なしにウィンドウをソートされた順序で維持する方法を理解するのに苦労しています。誰か説明できますか？O(N)

4

1 に答える 1

1

の場合にセグメントが有効であることを確認したあなたは正しいですmax(segment) - min(segment) + 1 = W。したがって、問題は のすべての長さWのセグメントの最小値と最大値を見つけることになりO(N)ます。

このために、deque Dを使用できます。分を見つけたいとします。D0 ベースのインデックス付けを想定して、要素のインデックスを に格納します。元Aの配列とします。

for i = 0 to N - 1:
  if D.first() == i - W:
    D.popFirst() <- this means that the element is too old, 
                    so we no longer care about it
  while not D.empty() and A[ D.last() ] >= A[i]:
    D.popLast()

  D.pushBack(i)

それぞれについて、これはindex の要素としてi最小値を与えます。[i - W + 1, i]D.first()

popFirst()から最初の要素を削除しDます。の最初の要素がからステップD以上W離れてiいる場合は、上記の間隔の最小値に寄与しないため、これを行う必要があります。

popLast()から最後の要素を削除しDます。ソート順を維持するためにこれを行います。 の最後の要素がDより大きい要素のインデックスである場合、 の最後A[i]に追加すると順序が崩れます。したがって、ソートされた状態を維持するために、最後の要素を削除し続ける必要があります。iDD

pushBack()の末尾に要素を追加しますD。それを追加した後、D間違いなくソートされたままになります。

これはO(1)(min を見つけるため、上記の疑似コードは です) 各要素が最大 1 回O(n)プッシュおよびポップされるためです。D

これDは、常に 内の関連付けられた値でソートされたインデックスのスライディング ウィンドウになるため、機能しAます。この順序を破る要素にいる場合D、順序が復元されるまで (スライディング ウィンドウ) から要素をポップできます。新しい要素はポップしている要素よりも小さいため、それらが解決に貢献できる方法はありません。

D:startとend. _ 次にD、長さの配列を作成Nすれば完了です。

于 2012-09-26T09:34:47.647 に答える