每天一道leetcode-74 在二维数组中搜索n
- 2019 年 10 月 4 日
- 筆記
前言
这道题目只需要一些简单的java语法知识，就可以看懂。
题目
leetcode-74 在二维数组中搜索一个数
分类(tag):二分查找这一类
英文链接：
https://leetcode.com/problems/search-a-2d-matrix/
中文链接：
https://leetcode-cn.com/problems/search-a-2d-matrix/
题目详述
编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
- 每行中的整数从左到右按升序排列。
- 每行的第一个整数大于前一行的最后一个整数。
示例 1:
输入:matrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ] target = 3输出: true
示例 2:
输入:matrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ] target = 13输出: false
题目详解
第一种方法
思路
- 这道题多数人看到这道题的时候，肯定就是想到剑指offer的思路.就是比较矩阵的右上角的数与target的大小，如果target比这个矩阵右上角的数大，由于矩阵的右上角元素A是A所在行的最大的值，所以target肯定不在A所在的行了，所以这时候就应该就在除去第一行的剩下的行中去找这个target;
- 如果target比矩阵右上角的数A小，那么由于A所在的列中A是最小的，那么target就在除去最右边的列的其它的列；
- 如果相等，返回true;
代码
class Solution { public boolean searchMatrix(int[][] matrix, int target) { if(matrix.length == 0) return false; int rowIndex = 0;//代表下标 int colIndex = matrix[0].length - 1;//代表下标 while(rowIndex < matrix.length && colIndex >=0) { if(target == matrix[rowIndex][colIndex]) return true; else if(target > matrix[rowIndex][colIndex]) rowIndex++; else colIndex--; } return false; } }
代码11到12行就是思路中第一步的体现，13-14行就是思路中第二步的体现。
第二种方法
思路
- 前面已经说了，这道题的分类是属于二分查找的这一类，所以肯定可以使用二分查找这个方法去解决，关键是如何转换为二分查找。
- 二分查找的话关键是要找到中间的值，大于这个中间值，就是往右半边去找，小于这个中间值，就是往左半边去找，这里我结合我的代码进行讲解好一些。
代码
class Solution { public boolean searchMatrix(int[][] matrix, int target) { if(matrix.length == 0) return false; int n = matrix[0].length; int left = 0; int right = matrix.length*matrix[0].length - 1; while(left <= right) { int mid = left + (right - left) / 2; if(target == matrix[mid/n][mid%n]) return true; else if(target < matrix[mid/n][mid%n]) right = mid - 1; else left = mid + 1; } return false; } }
我举一个例子方便大家理解。
示例 1:
输入:matrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ] target = 3输出: true
- 在这个示例中，1,3,5,7是第一行，10,11,16,20是第二行，23,30,34,50是第三行。总共有3*4=12个数，按照从0开始的方式，所以left=0,right=12-1=11,也就是代码6-7行所示；
- mid是二者去中间值，没毛病，mid=5第10行所示；
- 难点就在于matrix[mid/n][mid%n]的理解，就是对于一个下标如何确定它在二维数组中的位置，对于二维数组中，1来说，1是第0个数，第0/4行，3是第一个数，第0/4行，5是第2个数，第0/4行，7是第3个数，第0/4行，10是第4个数，第4/4行，11是5个数，第5/4行……..观察规律可知，行数就是用它的下标值去除以列的长度（matrix[0].length）也就是4；
- 同理对于列来说，1是第0个数，第0%4=0列，3是第1个数，第1%4=1列，5是第2个数，第2%4=2列，7是第3个数，第3%4列，10是第4个数，第4%4=0列…….观察规律可知，列数就是用它的下标值去对于4（matrix[0].length）取余。
- 所以mid的下标对应的二维数组中的数就是matrix[mid/4][mid%4];
结果展示
5ms的是二分查找的结果，比《剑指offer》还快了2ms。
结束语
每天一刷leetcode,10.28号打卡~
