MxN
行と列が並べ替えられた行列 ( ) があるとします。
- 各行のすべての要素は昇順で配置されます
- 各列のすべての要素は昇順で配置されます
- すべての要素は整数です
それ以外の仮定はできない
例:
[1 5 8 20]
[2 9 19 21]
[12 15 25 30]
特定の数値が行列に存在するかどうかを確認する必要があります (基本検索)。私は実行するアルゴリズムを持っていますO(n)
int row = 0;
int col = N-1;
while (row < M && col >= 0) {
if (mat[row][col] == elem) {
return true;
} else if (mat[row][col] > elem) {
col--;
} else {
row++;
}
}
しかし、私はO(log (MxN)) == O(Log(n))
解決策を求められました。何か案は??