东莞软件外包公司,网站导航结构的优化,怎么样建立一个网站,网站设计西安学习题目描述
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性#xff1a;
每行的元素从左到右升序排列。 每列的元素从上到下升序排列。 题目分析
通过分析矩阵的特点发现#xff0c;其左下角和右上角可以看作一个“二叉搜索树的根节…题目描述
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性
每行的元素从左到右升序排列。 每列的元素从上到下升序排列。 题目分析
通过分析矩阵的特点发现其左下角和右上角可以看作一个“二叉搜索树的根节点”一侧分支元素更小另一侧分支元素更大因此可以通过对比根节点与target的大小动态更新根节点(调整矩阵的下和左边界或者上/右边界)来找出target.以左下角元素为“根节点”为例进行分析 如果左下角元素大于target则target一定在左下角元素所在行的上方此时更新矩阵的下边界 如果左下角元素小于target则target一定在该元素所在列的右方此时更新矩阵的左边界 当左下角元素等于target时找到目标值返回true 当左下角元素的行索引或者列索引越界时表示没有找到目标返回false。
Code
class Solution {
public:bool searchMatrix(vectorvectorint matrix, int target) {if (matrix.empty()) {return false;}int row matrix.size() - 1, col 0;while (row 0 col matrix[0].size()) {if (matrix[row][col] target) {return true;} else if (matrix[row][col] target) {--row;} else {col;}}return false;}
};
