LeetCode100之搜索二维矩阵(46)--Java

1.问题描述

        给你一个满足下述两条属性的 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

        难度等级

        中等

        题目链接

        搜索二维矩阵

2.解题思路

        这道搜索二维矩阵的题比较常规，话不多说，直接开干。

        因为这是一个已经排好序的二维矩阵，每一行的第一个整数一定大于上一行的所有整数，所以我们可以先判断target是否在这个矩阵内，再进行搜索。如果target小于矩阵中最小的数或者target大于矩阵中最大的数，那就不用搜索了，肯定不在。

        //判断target是否小于矩阵中最小的数if(matrix[0][0] > target){return false;}//判断target是否大于矩阵中最大的数if(matrix[matrix.length-1][matrix[0].length-1] < target){return false;}

        接着，我们根据矩阵递增的特征，通过比较每一行的最后一个数与target的大小关系，可以定位到target可能处于矩阵的哪一行，用一个循环不断比较，当出现第一个大于或等于target的数时，target就处在那个数所在的行。

        //判断target可能位于哪一行矩阵中int row = 0;while(row < matrix.length && matrix[row][matrix[0].length-1] < target){row++;}

        然后，就是对我们找到的这一行进行常规的二分查找了，设置左右指针和二分指针，不断比较二分值与target的关系，不断缩小查找的范围，直到最终找到target的位置或者左右指针越界。

        //左右指针和二分指针int left = 0;int right = matrix[row].length - 1;int mid = 0;//判断target是否真的在我们筛选出来的矩阵中while(left <= right){//更新二分指针mid = (right - left) / 2 + left;//判断中间值是否为我们要找的数if(matrix[row][mid] == target){return true;}//若中间值小于目标值if(matrix[row][mid] < target){left = mid + 1;}//若中间值大于目标值if(matrix[row][mid] > target){right = mid - 1;}}

        最后，根据查找结果返回对应的答案即可。

3.代码展示

class Solution {public boolean searchMatrix(int[][] matrix, int target) {//判断target是否小于矩阵中最小的数if(matrix[0][0] > target){return false;}//判断target是否大于矩阵中最大的数if(matrix[matrix.length-1][matrix[0].length-1] < target){return false;}//判断target可能位于哪一行矩阵中int row = 0;while(row < matrix.length && matrix[row][matrix[0].length-1] < target){row++;}//左右指针和二分指针int left = 0;int right = matrix[row].length - 1;int mid = 0;//判断target是否真的在我们筛选出来的矩阵中while(left <= right){//更新二分指针mid = (right - left) / 2 + left;//判断中间值是否为我们要找的数if(matrix[row][mid] == target){return true;}//若中间值小于目标值if(matrix[row][mid] < target){left = mid + 1;}//若中间值大于目标值if(matrix[row][mid] > target){right = mid - 1;}}//若循环结束还是没有找到，说明target不在矩阵中return false;}
}

4.总结

        这道题，如果对二分查找熟练的话，其实理解起来不难，要做出来也不难，只要定位到target在矩阵的哪一行，就变成了常规的二分查找了。这道题就简单水到这里，祝大家刷题愉快，早日拿到心仪的offer~