海口免费自助建站模板,梧州自助建站seo,自己制作头像的软件,淘宝客合伙人网站建设给你一个满足下述两条属性的 m x n 整数矩阵#xff1a; 每行中的整数从左到右按非严格递增顺序排列。 每行的第一个整数大于前一行的最后一个整数。 给你一个整数 target #xff0c;如果 target 在矩阵中#xff0c;返回 true #xff1b;否则#xff0c;返回 false 。 …给你一个满足下述两条属性的 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 − 10 4 -10^4 −104 matrix[i][j], target 10 4 10^4 104 知识点 数组、矩阵、二分查找、排除法 解1非常暴力 核心思想定义辅助数组存储所有元素因为每一行的第一个元素大于上一行的最后一个元素因此可以这么操作然后对这个辅助数组进行二分查找。
时间复杂度 O ( m n ) O(mn) O(mn)。 空间复杂度 O ( m n ) O(mn) O(mn)。
class Solution {public boolean searchMatrix(int[][] matrix, int target) {//获取行数、列数int m matrix.length;int n matrix[0].length;//定义辅助数组存储所有元素int[] nums new int[m * n];for (int i 0; i m; i) {for (int j 0; j n; j) {nums[i * n j] matrix[i][j];}}//定义二分查找的指针int low 0;int high m * n - 1;//只要两个指针不重合就继续循环while (low high) {//获取中位数int mid (low high) / 2;//判断是否存在if (nums[mid] target) {return true;} else if (nums[mid] target) {high mid - 1;} else {low mid 1;}}//未找到return false;}
}解2排除法 核心思想同 #240. 搜索二维矩阵Ⅱ。
时间复杂度 O ( m n ) O(mn) O(mn)。 空间复杂度 O ( 1 ) O(1) O(1)。未使用辅助数组仅使用int类型的辅助变量。
class Solution {public boolean searchMatrix(int[][] matrix, int target) {//获取行数、列数int m matrix.length;int n matrix[0].length;//从右上角开始找int i 0;int j n - 1;//只要还有元素就继续循环while (i m j 0) {//找到元素返回if (matrix[i][j] target) {return true;}//若当前元素target则遍历前面一列else if (matrix[i][j] target) {j--;}//否则遍历下面一行else {i;}}//此时表明不存在元素return false;}
}解3二分查找 核心思想在形式上将矩阵所有元素放在一个数组中因为每一行的第一个元素大于上一行的最后一个元素因此可以这么操作在实际上通过matrix[i/n][i%n]获取mid在matrix中对应的元素然后使用二分查找
时间复杂度 O ( l o g ( m n ) ) O(log (mn)) O(log(mn))。 空间复杂度 O ( 1 ) O(1) O(1)。未使用辅助数组。
class Solution {public boolean searchMatrix(int[][] matrix, int target) {//获取行数、列数int m matrix.length;int n matrix[0].length;//定义二分查找的指针int low 0;int high m * n - 1;//只要两个指针不重合就继续循环while (low high) {//获取中位数int mid (low high) / 2;//获取矩阵对应的mid元素int item matrix[mid / n][mid % n];//判断是否存在if (item target) {return true;} else if (item target) {high mid - 1;} else {low mid 1;}}//未找到return false;}
}参考 1、灵神题解
