每天一道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