友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
240. Search a 2D Matrix II
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
-
Integers in each row are sorted in ascending from left to right.
-
Integers in each column are sorted in ascending from top to bottom.
Example:
Consider the following matrix:
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]Given target = 5, return true.
Given target = 20, 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
25
26
27
28
/**
* Runtime: 5 ms, faster than 99.96% of Java online submissions for Search a 2D Matrix II.
*
* Memory Usage: 50.3 MB, less than 5.66% of Java online submissions for Search a 2D Matrix II.
*
* Copy from: https://leetcode.com/problems/search-a-2d-matrix-ii/discuss/66140/My-concise-O(m%2Bn)-Java-solution[(1) My concise O(m+n) Java solution - LeetCode Discuss]
*
* @author D瓜哥 · https://www.diguage.com
* @since 2020-01-23 10:04
*/
public boolean searchMatrix(int[][] matrix, int target) {
if (Objects.isNull(matrix) || matrix.length == 0) {
return false;
}
int column = 0;
int row = matrix[0].length - 1;
while (column < matrix.length && 0 <= row) {
int value = matrix[column][row];
if (value == target) {
return true;
} else if (value < target) {
column++;
} else if (value > target) {
row--;
}
}
return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2024-09-15 18:14:17
*/
public boolean searchMatrix(int[][] matrix, int target) {
int row = 0, column = matrix[0].length - 1;
while (row < matrix.length && 0 <= column) {
int num = matrix[row][column];
if (num == target) {
return true;
} else if (target < num) {
column--;
} else {
row++;
}
}
return false;
}