-3

数値の配列とスライディング ウィンドウのサイズが与えられた場合、すべてのスライディング ウィンドウで最大数を取得する方法は?

たとえば、入力配列が {2, 3, 4, 2, 6, 2, 5, 1} で、スライディング ウィンドウのサイズが 3 の場合、最大値の出力は {4, 4, 6, 6, 6, 5}。スライディング ウィンドウのサイズは、渡される変数です。

スライディング ウィンドウは基本的に、特定のインデックスで始まる元の配列の部分配列です。たとえば、インデックス 0、サイズ 3 では、最初の 3 つの要素です。インデックス 1、サイズ 3 では、2 番目、3 番目、4 番目の要素です。

これを Java や他のプログラミング言語でどのように解決しますか? または、必要に応じて疑似コード。

（注：これは宿題の質問ではありません。私が独自の解決策を持っているサイトで見つけた質問ですが、他の人と比較したいので、後で私の解決策も投稿します）

4

3 に答える 3

1

で行うことができますO(N*Log(W))。ここで、Nは配列Wのサイズで、 はスライディング ウィンドウのサイズです。

二分木を使用して最初の数値を格納しWます。次のN-W手順ではmax、ツリーから出力の値を取得し、現在の位置にある要素をツリーに追加しi、ツリーから要素を削除しi-Wます。これらの操作はすべてO(Log(W))、全体のタイミングについては次のO(N*Log(W))とおりです。

int[] data = new int[] {2, 3, 4, 2, 6, 2, 5, 1};
int W = 3;
TreeMap<Integer,Integer> counts = new TreeMap<Integer,Integer>();
for (int i = 0 ; i != W ; i++) {
    if (counts.containsKey(data[i])) {
        counts.put(data[i], counts.get(data[i])+1);
    } else {
        counts.put(data[i], 1);
    }
}
for (int i = W ; i != data.length ; i++) {
    Integer max = counts.lastKey();
    System.out.println(max);
    int tmp = counts.get(data[i-W])-1;
    if (tmp != 0) {
        counts.put(data[i-W], tmp);
    } else {
        counts.remove(data[i-W]);
    }
    if (counts.containsKey(data[i])) {
        counts.put(data[i], counts.get(data[i])+1);
    } else {
        counts.put(data[i], 1);
    }
}
System.out.println(counts.lastKey());

ideone のデモ。

于 2013-07-17T19:54:40.583 に答える