网站建设与管理好吗,广州白云最新消息,php网站制作工具,视差设计网站一.题目要求
给你一个满足下述两条属性的 m x n 整数矩阵#xff1a;
每行中的整数从左到右按非严格递增顺序排列。每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target #xff0c;如果 target 在矩阵中#xff0c;返回 true #xff1b;否则#xff0c;…一.题目要求
给你一个满足下述两条属性的 m x n 整数矩阵
每行中的整数从左到右按非严格递增顺序排列。每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target 如果 target 在矩阵中返回 true 否则返回 false 。
二.题目难度
中等
三.输入样例
示例 1 输入matrix [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target 3 输出true
示例 2 输入matrix [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target 13 输出false
提示 m matrix.length n matrix[i].length 1 m, n 100 -104 matrix[i][j], target 104
四.解题思路
解法1先对每列第一个元素二分再二分查找符合条件的某一行。时间复杂度 O ( l o g m l o g n ) O(logmlogn) O(logmlogn) 解法2类似BST从右上角开始查找写法较简单时间复杂度 O ( l o g ( m ∗ n ) ) O(log(m∗n)) O(log(m∗n))
五.代码实现
解2
class Solution {
public:bool searchMatrix(vectorvectorint matrix, int target) {int row matrix.size();int col matrix[0].size();for (int i 0, j col - 1; i row j 0;matrix[i][j] target ? j-- : i) {if (matrix[i][j] target)return true;}return false;}
};解1
class Solution {
public:bool searchMatrix(vectorvectorint matrix, int target) {int rowl 0;int rowr matrix.size() - 1;int rowmid (rowl rowr) / 2;while (rowl rowr) {rowmid (rowl rowr) / 2;if (matrix[rowmid][0] target)return true;if (matrix[rowmid][0] target) {rowr - 1;}else if (matrix[rowmid][0] target) {rowl 1;}}int l 0;int r matrix[0].size() - 1;int m (l r) / 2;int row;if (rowl rowr)row rowr;elserow rowl;if (row 0 || row matrix.size())return false;while (l r) {m (l r) / 2;if (matrix[row][m] target)return true;if (matrix[row][m] target) {r - 1;} else if (matrix[row][m] target) {l 1;}}return false;}
};六.题目总结
–
