手机特殊网站,企业标准化建设,取消wordpress还原,百度分公司问题背景
给你一个满足下述两条属性的 m n m \times n mn 整数矩阵#xff1a;
每行中的整数从左到右按非严格递增顺序排列。每行的第一个整数大于前一行的最后一个整数。 给你一个整数 t a r g e t target target#xff0c;如果 t a r g e t target target 在矩阵中
每行中的整数从左到右按非严格递增顺序排列。每行的第一个整数大于前一行的最后一个整数。 给你一个整数 t a r g e t target target如果 t a r g e t target target 在矩阵中返回 t r u e true true否则返回 f a l s e false false。
数据约束 m m a t r i x . l e n g t h m matrix.length mmatrix.length n m a t r i x [ i ] . l e n g t h n matrix[i].length nmatrix[i].length 1 ≤ m , n ≤ 100 1 \le m, n \le 100 1≤m,n≤100 − 1 0 4 ≤ m a t r i x [ i ] [ j ] , t a r g e t ≤ 1 0 4 -10 ^ 4 \le matrix[i][j], target \le 10 ^ 4 −104≤matrix[i][j],target≤104
解题过程
题目保证整个矩阵中的元素从上到下从左到右依次递增也就是可以展开成一个递增的一维数组可以用下标映射的方式在这个虚拟的一维矩阵中进行二分搜索时间复杂度为 O ( l o g ( m n ) ) O(log(mn)) O(log(mn))。
还可以用排除法参考 搜索二维矩阵 II。从矩阵的右上角开始每次比较能够去掉一行或一列相当于查找抽象的二叉搜索树时间复杂度大致在 O ( m n ) O(m n) O(mn) 这个量级。 具体实现
整体二分
class Solution {public boolean searchMatrix(int[][] matrix, int target) {int m matrix.length, n matrix[0].length;int left 0, right m * n;while(left right) {int mid left ((right - left) 1);int cur matrix[mid / n][mid % n];if(cur target) {return true;}if(cur target) {left mid 1;} else {right mid;}}return false;}
}查找抽象二叉搜索树
class Solution {public boolean searchMatrix(int[][] matrix, int target) {int i 0;int j matrix[0].length - 1;while(i matrix.length j 0) {int cur matrix[i][j];if(cur target) {return true;}if(cur target) {i;} else {j--;}}return false;}
}
