74. 搜索二维矩阵文章目录[74. 搜索二维矩阵](https://leetcode.cn/problems/search-a-2d-matrix/)四种解题思路第一种暴力枚举O(m·n)第二种逐行二分O(m·log n)第三种两次二分O(log m log n) O(log(m·n))第四种模拟一维数组总结给你一个满足下述两条属性的m x n整数矩阵每行中的整数从左到右按非严格递增顺序排列。每行的第一个整数大于前一行的最后一个整数。给你一个整数target如果target在矩阵中返回true否则返回false。你必须编写一个时间复杂度为O(log(m * n))的解决方案。示例 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四种解题思路接下来我会带着你从 O(m·n) 一步步优化到 O(log(m·n))。第一种暴力枚举O(m·n)嵌套 for 循环逐个判断都没匹配就返回 false。这种做法一定会超时也不符合题目要求这里不展开。第二种逐行二分O(m·log n)对每一行各做一次二分查找。这是最常见的优化思路但它适用于“行与行之间整体不保证严格递增”的情况——比如下一行第一个元素不一定大于上一行最后一个元素。而这道题的二维数组整体是严格升序的所以这个做法还不够需要继续优化。第三种两次二分O(log m log n) O(log(m·n))从这里开始才是这道题能 AC 的解法。思路是第一次二分确定 target 如果存在应该在哪一行第二次二分在这一行里继续找。两次二分就能定位到 target。Java 代码演示classSolution{publicbooleansearchMatrix(int[][]matrix,inttarget){introwIndexbinarySearchFirstColumn(matrix,target);if(rowIndex0){returnfalse;}returnbinarySearchRow(matrix[rowIndex],target);}publicintbinarySearchFirstColumn(int[][]matrix,inttarget){intlow-1,highmatrix.length-1;while(lowhigh){intmid(high-low1)/2low;if(matrix[mid][0]target){lowmid;}else{highmid-1;}}returnlow;}publicbooleanbinarySearchRow(int[]row,inttarget){intlow0,highrow.length-1;while(lowhigh){intmid(high-low)/2low;if(row[mid]target){returntrue;}elseif(row[mid]target){highmid-1;}else{lowmid1;}}returnfalse;}}作者力扣官方题解 链接https://leetcode.cn/problems/search-a-2d-matrix/solutions/688117/sou-suo-er-wei-ju-zhen-by-leetcode-solut-vxui/来源力扣LeetCode 著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。Golang 代码演示funcsearchMatrix(matrix[][]int,targetint)bool{iflen(matrix)0||len(matrix[0])0{returnfalse}m,n:len(matrix),len(matrix[0])// 第一次二分定位行// 找第一个满足 matrix[row][n-1] target 的行top,bottom:0,m-1fortopbottom{mid:top(bottom-top)/2ifmatrix[mid][n-1]target{topmid1}else{bottommid}}row:top// 第二次二分在该行内查找left,right:0,n-1forleftright{mid:left(right-left)/2ifmatrix[row][mid]target{returntrue}elseifmatrix[row][mid]target{leftmid1}else{rightmid-1}}returnfalse}第四种模拟一维数组如果把二维数组按元素个数“摊平”对上面那个 3×4 的数组来说几乎所有人都会把第一行第一个元素当作第 1 个元素把第三行第四个元素当作第 12 个元素。我们就按这个逻辑模拟一维数组——整个数组长度为 12。那问题来了怎么把这个“脑海中模拟的一维数组”和真实的二维数组做映射这里直接给公式matrix[mid / n][mid % n]稍微推演一下就能明白mid / n 定位行mid % n 定位列。好现在按这个思路写代码。Java 代码演示classSolution{publicbooleansearchMatrix(int[][]matrix,inttarget){intmmatrix.length,nmatrix[0].length;intlow0,highm*n-1;while(lowhigh){intmid(high-low)/2low;intxmatrix[mid/n][mid%n];if(xtarget){lowmid1;}elseif(xtarget){highmid-1;}else{returntrue;}}returnfalse;}}作者力扣官方题解 链接https://leetcode.cn/problems/search-a-2d-matrix/solutions/688117/sou-suo-er-wei-ju-zhen-by-leetcode-solut-vxui/来源力扣LeetCode 著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。Golang 代码演示funcsearchMatrix(matrix[][]int,targetint)bool{m,n:len(matrix),len(matrix[0])l,r:0,m*n-1forlr{mid:l(r-l)/2ifmatrix[mid/n][mid%n]target{returntrue}elseifmatrix[mid/n][mid%n]target{lmid1}else{rmid-1}}returnfalse}总结本文是 《算法题目解析系列》 的第 [32] 篇本系列将持续更新每篇都提供清晰的思路与编程语言实现。欢迎关注第一时间获取更新。如果你有想看的题目也可以在评论区留言告诉我。