1

私は正方形の行列と、可能なすべての位置で行列内を移動する小さな正方形を持っています(行列の外には出ません)。このような重複の可能性があるすべての中で最小の数を見つける必要があります。

問題は、両方のサイズが数千に達する可能性があることです。それを行うための速い方法はありますか？

私は 1 つの方法を知っています。行列の代わりに配列があり、正方形の代わりにウィンドウがある場合、 dequeを使用して線形時間でそれを行うことができます。

前もって感謝します。

編集：例

マトリックス：

1 3 6 2 5
8 2 3 4 5
3 8 6 1 5
7 4 8 2 1
8 0 9 0 5

サイズ 3 の正方形の場合、合計 9 つのオーバーラップが可能です。重なり合うそれぞれの行列形式の最小数は次のとおりです。

1 1 1
2 1 1
0 0 0
4

1 に答える 1

1

O(k * n^2)あなたのdequeアイデアで可能です：

小さい正方形がk x kの場合、行列の 1 から までの要素の最初の行を反復し、行列の各列で 1 から、2 からなどkの要素の最小値を事前計算することにより、配列として扱います(この事前計算には最初の行は次のようになります。kk + 1O(k * n^2))

*********
1 3 6 2 5
8 2 3 4 5
3 8 6 1 5
*********
7 4 8 2 1
8 0 9 0 5

前述の事前計算により、各列の最小値が得られるため、問題を 1 次元配列の問題に減らすことができます。

次に、2 から までの要素の行を続けk + 1ます。

1 3 6 2 5
*********
8 2 3 4 5
3 8 6 1 5
7 4 8 2 1
*********
8 0 9 0 5

行があり、事前計算によってそれらを基本的な配列に減らすことができるため、O(n)それぞれを解くことができます。O(n)

于 2013-04-12T10:54:37.633 に答える