次のようなNxMの行列にある数値が含まれているかどうかを探索するには？
-4 -1 4 5
-3 0 6 10
1 8 11 15
17 19 22 30
行列の各行、各列ともにソートされている。
普通に考えると各行(または各列)を二分探索して、O(MlogN) or O(NlogM)だと思うけど。
もっと高速に解くには？
あー、これは四分探索になるんだな。
次の例で考える。N=8,M=8
005 006 008 010 013 014 045 059
015 016 058 066 081 106 134 140
019 053 062 074 145 173 189 203
034 057 068 102 158 213 238 245
041 058 098 177 246 256 277 335
058 097 134 226 297 329 387 410
061 129 172 276 344 402 488 549
067 134 180 299 359 403 539 569
ここから「106」が含まれるか調べたいとき。
各小行列の右下の要素(rb)がその小行列中の最大要素、左上(lt)の要素がその小行列中の最小要素であることに注目。
まず4分割して、各ブロックのltとrbの範囲内に探したい要素(x)が含まれているかlt <= x <= rbなチェックする。
005 006 008 010 | 013 014 045 059
015 016 058 066 | 081 106 134 140
019 053 062 074 | 145 173 189 203
034 057 068 102 | 158 213 238 245
---------------------------------
041 058 098 177 | 246 256 277 335
058 097 134 226 | 297 329 387 410
061 129 172 276 | 344 402 488 549
067 134 180 299 | 359 403 539 569
今回の場合、次の2ブロックが該当
013 014 045 059
081 106 134 140
145 173 189 203
158 213 238 245
041 058 098 177
058 097 134 226
061 129 172 276
067 134 180 299
各ブロックについて同じ様に4分割して、lt <= x <= rbなチェックをする。
一番上のブロックだけ例示すると
013 014 | 045 059
081 106 | 134 140
-----------------
145 173 | 189 203
158 213 | 238 245
チェックを通るのは
013 014
081 106
のみ。小行列が1x1になるまで再帰してやれば良い。
計算量はいくらだ？O(log(N+M))でいけるかな？
なんか候補がいっぱい残りそうで微妙？
Javaで適当に実装すると、↓こんな感じ
/**
* 行列を四分割する(やっつけ実装)
*/
public static int[][][] divide(int[][] matrix, int N, int M) {
int n1 = N / 2;
int n2 = N - n1;
int m1 = M / 2;
int m2 = M - m1;
int[][] m11 = new int[n1][m1];
for (int i = 0; i < n1; i++) {
for (int j = 0; j < m1; j++) {
m11[i][j] = matrix[i][j];
}
}
int[][] m12 = new int[n1][m2];
for (int i = 0; i < n1; i++) {
for (int j = 0; j < m2; j++) {
m12[i][j] = matrix[i][m1 + j];
}
}
int[][] m21 = new int[n2][m1];
for (int i = 0; i < n2; i++) {
for (int j = 0; j < m1; j++) {
m21[i][j] = matrix[n1 + i][j];
}
}
int[][] m22 = new int[n2][m2];
for (int i = 0; i < n2; i++) {
for (int j = 0; j < m2; j++) {
m22[i][j] = matrix[n1 + i][m1 + j];
}
}
int[][][] ret = { m11, m12, m21, m22 };
return ret;
}
/**
* 二次元二分探索?
*/
public static boolean binarySearch(int[][] matrix, int N, int M, int x) {
if (N == 0 || M == 0) {
return false;
} else if (N == 1 && M == 1) {
return matrix[0][0] == x;
} else {
int[][][] divided = divide(matrix, N, M);
for (int[][] mat : divided) {
int n = mat.length;
if (n > 0) {
int m = mat[0].length;
if (m > 0) {
int lt = mat[0][0];
int rb = mat[n - 1][m - 1];
if (lt <= x && x <= rb) {
if (binarySearch(mat, n, m, x)) {
return true;
}
}
}
}
}
}
return false;
}
試してみたけど、各行を2分探索した方が10倍くらい速かった。。。
行列作りまくってる所が遅いな。そもそもアルゴリズム的にどうなんだ。