每天一道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號打卡~