网站策划设计建设,免费虚拟主机网站源码,宁波手机网站制作,广州建设交易中心网站1. 题目
编写一个高效的算法来判断 m x n 矩阵中#xff0c;是否存在一个目标值。该矩阵具有如下特性#xff1a;
每行中的整数从左到右按升序排列。 每行的第一个整数大于前一行的最后一个整数。
示例 1:
输入:
matrix [[1, 3, 5, 7],[10, 11, 16, 20],[23, 30, 34,…1. 题目
编写一个高效的算法来判断 m x n 矩阵中是否存在一个目标值。该矩阵具有如下特性
每行中的整数从左到右按升序排列。 每行的第一个整数大于前一行的最后一个整数。
示例 1:
输入:
matrix [[1, 3, 5, 7],[10, 11, 16, 20],[23, 30, 34, 50]
]
target 3
输出: true来源力扣LeetCode 链接https://leetcode-cn.com/problems/search-a-2d-matrix 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 二分查找
参考 二分查找
先在第一列二分查找比target小的最后一个数是谁在该行二分查找target
class Solution {
public:bool searchMatrix(vectorvectorint matrix, int target) {if(matrix.size()0 || matrix[0].size() 0)return false;//在第一列搜索最后一个比我小的int i, r matrix.size(), c matrix[0].size();int left 0, right r-1, mid;while(left right){mid left ((right-left)1);if(matrix[mid][0] target)return true;if(matrix[mid][0] target){if(mid r-1 || matrix[mid1][0] target)break;//mid行搜索即可elseleft mid1;}elseright mid-1;}int R mid;left 0, right c-1;while(left right){mid left ((right-left)1);if(matrix[R][mid] target)return true;if(matrix[R][mid] target) left mid1;elseright mid-1;}return false;}
};转换成1维数组即可变成标准二分查找
class Solution {public:bool searchMatrix(vectorvectorint matrix, int target) {if(matrix.size()0 || matrix[0].size() 0)return false;int i, r matrix.size(), c matrix[0].size();// 二分查找int left 0, right r * c - 1;//关键点int mid, val;while (left right) {mid (left right) / 2;val matrix[mid/c][mid%c];//关键地方if (target val) return true;else {if (target val) right mid - 1;else left mid 1;}}return false;}
};
