本文主要是介绍LeetCode 刷题 [C++] 第240题.搜索二维矩阵 II,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目描述
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性:
每行的元素从左到右升序排列。
每列的元素从上到下升序排列。
题目分析
- 通过分析矩阵的特点发现,其左下角和右上角可以看作一个“二叉搜索树的根节点”,一侧分支元素更小,另一侧分支元素更大;
- 因此,可以通过对比根节点与target的大小,动态更新根节点(调整矩阵的下和左边界或者上/右边界),来找出target.
- 以左下角元素为“根节点”为例进行分析:
如果左下角元素大于target,则target一定在左下角元素所在行的上方,此时,更新矩阵的下边界;
如果左下角元素小于target,则target一定在该元素所在列的右方,此时,更新矩阵的左边界;
当左下角元素等于target时,找到目标值,返回true;
当左下角元素的行索引或者列索引越界时,表示没有找到目标,返回false。
Code
class Solution {
public:bool searchMatrix(vector<vector<int>>& 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;}
};
这篇关于LeetCode 刷题 [C++] 第240题.搜索二维矩阵 II的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!