题目描述：
一个二维矩阵 $n\times m$ ，每行每列都是升序，给出一个 target判断矩阵中是否存在该值。
数据范围：
$1\le n,m\le 300$
题解：
可以对每一行或者每一列进行二分查找，复杂度为 $O(m\log(n))$ .
但是换一个角度，从第一行的最右边看起，往左是递减，往下是递增。刚好是一个二叉搜索树，可以根据二叉搜索树的性质快速找到答案。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const static int INF = 0x3f3f3f3f;
static void optimize_cpp_stdio() { ios::sync_with_stdio(false), cin.tie(0); }
bool searchMatrix(vector<vector<int>> &matrix, int target)
{
optimize_cpp_stdio();
int n = matrix.size(), m = matrix[0].size();
int x = 0, y = m - 1, ans = 0;
while (x < n && y >= 0)
{
if (matrix[x][y] == target)
{
ans = 1;
break;
}
else if (matrix[x][y] > target)
y--;
else
x++;
}
return ans;
}
};
|