锐客网

  1. 首页 > it技术 > >

java|【力扣算法】240-搜索二维矩阵II

java算法leetcode二分查找分治法

题目 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：

  • 每行的元素从左到右升序排列。
  • 每列的元素从上到下升序排列。
示例:
现有矩阵 matrix 如下：
[ [1,4,7, 11, 15], [2,5,8, 12, 19], [3,6,9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30] ]

给定 target = 5，返回 true。
给定 target = 20，返回 false。
题解 无官方题解
网友题解：
  • 从最右上角的元素开始找，如果这个元素比target大，则说明找更小的，往左走；如果这个元素比target小，则说明应该找更大的，往下走。
  • 画个图看代码就很容易理解，总之就是从右上角开始找，如果矩阵的元素小了就往下走，如果矩阵元素大了就往左走。如果某个时刻相等了，就说明找到了，如果一直走出矩阵边界了还没找到，则说明不存在。
class Solution { public boolean searchMatrix(int[][] matrix, int target) { if(matrix == null || matrix.length < 1 || matrix[0].length < 1){ return false; } //起点为最左上角的元素 int row = 0, col = matrix[0].length - 1; //判断当前数组元素和target，如果当前大于target，往左走；小与target，往下走 while(row < matrix.length && col >= 0){ if(matrix[row][col] < target){ row++; }else if(matrix[row][col] > target){ col--; }else{ return true; } } //走出边界了还没找到，说明不存在，返回false return false; } }

执行用时 : 13 ms, 在Search a 2D Matrix II的Java提交中击败了86.52% 的用户
内存消耗 : 51.9 MB, 在Search a 2D Matrix II的Java提交中击败了34.62% 的用户
感想 写了个很慢的解答。。。思路就是很简单的分治，从左上角出发分为右侧、下侧、右下三部分去查找。
感觉看到别人从右上或者左下开始查找的思路，一下就发现自己的愚蠢了。。。右下和左下出发感觉就相当于二分法了，简单多了。
执行用时 : 66 ms, 在Search a 2D Matrix II的Java提交中击败了5.04% 的用户
【java|【力扣算法】240-搜索二维矩阵II】内存消耗 : 51.9 MB, 在Search a 2D Matrix II的Java提交中击败了34.84% 的用户
class Solution { public boolean searchMatrix(int[][] matrix, int target) { return searchMatrixSub(matrix, target, 0, 0); } private boolean searchMatrixSub(int[][] matrix, int target, int row, int col){ if(matrix.length == 0) return false; else if(matrix[0].length == 0) return false; if(matrix[row][col] == target) return true; else if(matrix[row][col]>target) return false; else { boolean moreRow = (rowtarget) return false; else { if(rowtarget) return false; else { if(col

    推荐阅读


    上一篇：Android基础|后台服务中弹出激活设备管理器界面失败原因定位

    下一篇：【力扣算法】57-插入区间