友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
74. 搜索二维矩阵
给你一个满足下述两条属性的 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 == matrix.length -
n == matrix[i].length -
1 <= m, n <= 100 -
-104 <= matrix[i][j], target <= 104
思路分析
由于矩阵同行有序，下一行比上一行大，所以，通过将矩阵容量转换成坐标，把每一行“拼接”起来就是一个有序数组，可以用二分查找解决问题。
也可以使用 240. 搜索二维矩阵 II 类似的解法，从左下角或者右上角开始，排除行或列来解答。
-
一刷
-
二刷
-
三刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-04-23 18:20:50
*/
public boolean searchMatrix(int[][] matrix, int target) {
int row = matrix.length;
int column = matrix[0].length;
int left = 0, right = row * column - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
int num = matrix[mid / column][mid % column];
if (num == target) {
return true;
} else if (target < num) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-11-18 22:23:27
*/
public boolean searchMatrix(int[][] matrix, int target) {
int row = matrix.length;
int column = matrix[0].length;
int low = 0, high = row * column - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
int r = mid / column;
int c = mid % column;
int num = matrix[r][c];
if (num == target) {
return true;
}
if (num < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-11-18 22:23:27
*/
public boolean searchMatrix(int[][] matrix, int target) {
int r = 0, c = matrix[r].length - 1;
while (r < matrix.length && 0 <= c) {
int num = matrix[r][c];
if (num == target) {
return true;
}
if (target < num) {
c--;
} else {
r++;
}
}
return false;
}