每天一道leetcode240-在二维数组中搜索n升级版

• 2019 年 10 月 4 日
• 笔记

前言

这道题目只需要一些简单的java语法知识，就可以看懂。

题目

leetcode-240 在二维数组中搜索一个数Ⅱ

分类(tag):二分查找这一类

英文链接：

https://leetcode.com/problems/search-a-2d-matrix-ii/

中文链接：

https://leetcode-cn.com/problems/search-a-2d-matrix-ii/

题目详述

编写一个高效的算法来搜索 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。

昨天的题目：每天一道leetcode-74 在二维数组中搜索n

这道题和昨天的那道题不同地方是昨天的那道题每行的·最末尾的数字必然小于下一行的开头的数字，今天这个题目每行的·最末尾的数字与下一行的开头的数字没有必然的联系

题目详解

第一种方法

思路

1. 这道题多数人看到这道题的时候，肯定就是想到剑指offer的思路.就是比较矩阵的右上角的数与target的大小，如果target比这个矩阵右上角的数大，由于矩阵的右上角元素A是A所在行的最大的值，所以target肯定不在A所在的行了，所以这时候就应该就在除去第一行的剩下的行中去找这个target;
2. 如果target比矩阵右上角的数A小，那么由于A所在的列中A是最小的，那么target就在除去最右边的列的其它的列；
3. 如果相等，返回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行就是思路中第二步的体现。

第二种方法

思路

1. 前面已经说了，这道题的分类是属于二分查找的这一类，所以肯定可以使用二分查找这个方法去解决，关键是如何转换为二分查找。
2. 二分查找的话关键是要找到中间的值，由于这道题目是数字并不是依次递增的，所以无法利用昨天的那道题目的思路来解决；昨天的题目：每天一道leetcode-74 在二维数组中搜索n
3. 感觉微信名为NLogN的群友提供的思路，他看了我昨天的那道题目，然后和我说着到题目先按照第一列进行二分，这样确定了target可能在哪几行，然后他后续的的思路我对其进行了这样的改进，上面已经确定了在哪几行，然后再每一行中相当于一个数组找一个数target，继续二分查找；遍历完每一行，最后就可以确定target到底在不在。

代码

class Solution {      public boolean searchMatrix(int[][] matrix, int target) {          if(matrix.length == 0 || matrix[0].length == 0)              return false;          int begin = 0;          int end = matrix.length - 1;          int midRow = (begin + end) / 2;          while(begin <= end)          {              midRow = begin + (end - begin) / 2;              if(target == matrix[midRow][0])                  return true;              else if(target > matrix[midRow][0])                  begin = midRow + 1;              else                  end = midRow - 1;          }          for(int i=0;i<=midRow;i++)          {              int left = 0;              int right = matrix[0].length-1;              while(left <= right)              {                  int mid = left + (right-left)/2;                  if(matrix[i][mid] == target)                      return true;                  else if(matrix[i][mid] < target)                      left = mid + 1;                  else                      right = mid - 1;              }          }          return false;      }  }  

1. 第5行到第17行，就是确定target可能在哪几行，通过在第一列中进行二分查找，找到target可能在的行数；
2. 第18行代第32行代码，就是从第0行开始到在第一步中确定的target的行数，从每一行中利用二分查找去找target；

结果展示

7ms是剑指offer的方法，8m是二分查找的方法；

结束语

每天一刷leetcode,10.29号打卡~

END