微信小程序商城怎么开通,石家庄抖音seo,网站空间管理面板,注册建设网站的公司网站大家好#xff01;我是曾续缘#x1f497; 今天是《LeetCode 热题 100》系列 发车第 21 天 矩阵第 4 题 ❤️点赞 #x1f44d; 收藏 ⭐再看#xff0c;养成习惯 搜索二维矩阵 II 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性我是曾续缘 今天是《LeetCode 热题 100》系列 发车第 21 天 矩阵第 4 题 ❤️点赞 收藏 ⭐再看养成习惯 搜索二维矩阵 II 编写一个高效的算法来搜索 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提示 m matrix.lengthn matrix[i].length1 n, m 300-109 matrix[i][j] 109每行的所有元素从左到右升序排列每列的所有元素从上到下升序排列-109 target 109 难度 解题方法
对于矩阵中的某个点matrix[i][j]来说观察到向左移动数字减小向下移动数字增大类似于二分查找树的性质。同样地向上移动数字减小向右移动数字增大也类似于二分查找树。
如果我们限制只能向左或向下移动这就相当于在遍历二分查找树同理如果限制只能向右或向上移动也可以看作是在遍历二分查找树。
接下来我们需要找到二分查找树的根节点使其包含矩阵中的所有值。可以选择左下角和右上角两个点作为二分查找树的根节点。
以左下角为例
如果目标值大于当前值则向上移动。如果目标值小于当前值则向右移动。如果相等则直接返回 true。如果移出矩阵范围说明到达空结点返回 false。
Code
class Solution {public boolean searchMatrix(int[][] matrix, int target) {int m matrix.length, n matrix[0].length;int i 0, j n - 1; // 右上角while(i m j 0){if(matrix[i][j] target){return true;}if(matrix[i][j] target){j--;}else{i;}}return false;}
}
