题目
编写一个高效的算法来搜索 m x n
矩阵 matrix
中的一个目标值 target
。该矩阵具有以下特性:
- 每行的元素从左到右升序排列。
- 每列的元素从上到下升序排列。
示例 1:
输入: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]], target = 5 输出:true
示例 2:
输入: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]], target = 20 输出:false
提示:文章来源:https://www.toymoban.com/news/detail-658696.html
m == matrix.length
n == matrix[i].length
1 <= n, m <= 300
-10^9 <= matrix[i][j] <= 10^9
- 每行的所有元素从左到右升序排列
- 每列的所有元素从上到下升序排列
-10^9 <= target <= 10^9
解答
源代码
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
return dfs(matrix, 0, matrix[0].length - 1, target);
}
public boolean dfs(int[][] matrix, int i, int j, int target) {
if (i >= matrix.length || j < 0) {
return false;
}
if (matrix[i][j] == target) {
return true;
} else if (matrix[i][j] > target) {
return dfs(matrix, i, j - 1, target);
} else {
return dfs(matrix, i + 1, j, target);
}
}
}
总结
想用递归,但重点在于递归的起点在哪里。一开始我把递归的起点定在了左上角,这样做出来的算法其实比暴力破解还糟糕;把起点定在右上角才是正确的选择,此时当前元素的左边都比它小,下边都比它大。文章来源地址https://www.toymoban.com/news/detail-658696.html
到了这里,关于【LeetCode】240.搜索二维矩阵Ⅱ的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!