LeetCode74. 搜索二维矩阵（2024冬季每日一题 6）
给你一个满足下述两条属性的 m x n 整数矩阵：
- 每行中的整数从左到右按非严格递增顺序排列。
- 每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。
示例 1：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true
示例 2：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false
提示：
m
=
=
m
a
t
r
i
x
.
l
e
n
g
t
h
m == matrix.length
m==matrix.length
n
=
=
m
a
t
r
i
x
[
i
]
.
l
e
n
g
t
h
n == matrix[i].length
n==matrix[i].length
1
<
=
m
,
n
<
=
100
1 <= m, n <= 100
1<=m,n<=100
−
1
0
4
<
=
m
a
t
r
i
x
[
i
]
[
j
]
,
t
a
r
g
e
t
<
=
1
0
4
-10^4 <= matrix[i][j], target <= 10^4
−104<=matrix[i][j],target<=104
思路：
- 从右上角位置开始搜索
- 如果目标值大于当前值，则向下走一格（走到下一行）
- 如果目标值小于当前值，则向左走一列（走到前一列）
- 直到当前值等于目标值，则返回 true
- 如果走出了方格边界，则返回 false
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int n = matrix.size(), m = matrix[0].size();
int x = 0, y = m - 1;
while(true){
if(matrix[x][y] == target) return true;
else if(matrix[x][y] < target) x++;
else y--;
if(x >= n || y < 0) break;
}
return false;
}
};