4

シーケンスの変位を最大要素と最小要素の差と定義します。与えられた整数のシーケンスについて、長さ の連続するすべてのサブシーケンスの最大変位を見つけますm。

たとえば、シーケンスが [1, 5, 7, 0, 2, -4] で m = 3 の場合、

  • [1, 5, 7] の変位は 6 です。
  • [5, 7, 0] の変位は 7 です。
  • [7, 0, 2] の変位は 7 です。
  • [0, 2, -4] の変位は 6 です。
  • したがって、最大変位は 7 です。

入力シーケンスの長さを n とすると、以下の私のソリューションは O(nlog(m)) 時間で実行されます。より良い方法はありますか？私が見逃している線形時間アルゴリズムがあるに違いないと感じています。この質問の目的のために、私が気にするのは漸近的な時間の複雑さだけです。

#include <vector>
#include <set>
#include <iostream>
int find_max_displacement(std::vector<int> seq, int m){
    std::multiset<int> subseq;
    // insert the m items of first subsequence into tree
    for (int i = 0; i < m; i++){
        subseq.insert( seq[i] );
    }
    int max_disp = *subseq.rbegin() - *subseq.begin(); // max minus min
    for (int i = 0; i < seq.size() - m; i++){
        subseq.erase(subseq.find(seq[i]));  // kick oldest element out of subsequence
        subseq.insert( seq[i+m] );          // insert new element into subsequence
        int new_disp = *subseq.rbegin() - *subseq.begin();
        if (new_disp > max_disp){
            max_disp = new_disp;
        }
    }
    return max_disp;
}
int main(){
    std::vector<int> arr {1, 5, 7, 0, 2, -4};
    int max_disp = find_max_displacement(arr, 3);
    std::cout << max_disp << std::endl;
    return 0;
}
4

1 に答える 1

3

そうです、これには線形時間アルゴリズムがあります。スライド最大値を持つ配列とスライド最小値を持つ配列を計算し、これら 2 つの配列間の最大の差を見つけることができます。

線形時間でスライディング最大値を計算することは標準的な問題です。ここにはさまざまな手法の適切な説明があります。リンクが壊れた場合に備えて、そのリンクからの線形時間アルゴリズムの説明を次に示します。

ここで紹介するアルゴリズムは昇順最小アルゴリズムです。O(n) 時間と O(k) スペースが必要です。一般的な考え方は、ウィンドウ内の最小値を特定し、次にウィンドウの残りの最小値を特定するというものです。昇順の最小値の間の値は無視できます。

より形式的には、W を長さ k の値のベクトルとします。次のように、昇順の最小値 A のシーケンスを定義します。

A[0] を W の最小値とし、j>0 の場合、A[j] を W の最小値とし、インデックスは A[j-1] のインデックスより大きくします。(2 つの場所の最小値が同じ場合は、後の方を使用します。) 例:

 W = 5,2,8,6,4,7 
 A = 2,4,7

明らかに、A の長さは、W の最小値が W の最後の要素である場合は 1 であり、W が単調増加の場合は k です。ここで、V にウィンドウ W があり、昇順の最小ベクトル A がわかっているとします。ウィンドウを 1 つの位置に移動するとどうなるかを考えてみましょう。ウィンドウの最後に要素を 1 つ追加し、ウィンドウの先頭から要素を 1 つ削除します。新しく追加された要素を x とします。次に、Aは次のように更新できます

a: x 以上の A のすべての要素を削除します。

b: A に x を追加し、

c: ウィンドウから削除されている場合は、A の最初の要素を削除します。

ウィンドウを記録する必要はありません。必要なのは昇順の最小シーケンスだけです。ただし、シーケンス内のエントリがいつウィンドウから削除されるかを記録する必要があります。このため、A の要素が 2 つのフィールドを持っていると便利です。最初のフィールドは V からの値、つまり一部の i の V[i] で、2 番目のフィールドはエントリがウィンドウから消えるときのインデックスです。これは k エントリ後に発生します。

A の長さには制限があり、A はキューであるため、リング バッファーに格納するのが自然です。

ステップ (b) と (c) は、重要な代替手段がなくても簡単です。ステップ (a) では、新しく追加された x より小さい A の最後の値を見つける必要があります。一見すると、A の二分探索が最適であるように見えるかもしれません。これはそうではありません; 最適な検索は、単純なループで後ろから前に行うことです。

証明は簡単です。線形検索ループは、削除ごとに O(1) の時間コストで要素を 1 つずつ削除します。平均して、A からの削除の数は、追加の数と同じです。結果として、ウィンドウを 1 箇所移動する平均時間コストは O(1) になります。

于 2014-12-05T10:41:20.620 に答える