文章目錄

• 1 題目理解
• 2 二分

1 題目理解

輸入：一個mxn的int數(shù)組matrix，這個數(shù)組每一行按照從小到大排序，并且下一行的第一個值大于上一行的最后一個值。一個int值target
返回：target在matrix中是否存在。存在返回true。

2 二分

我們可以把這個數(shù)組看做是一個有序數(shù)組。數(shù)組下表從0到m*n-1。

class Solution {public boolean searchMatrix(int[][] matrix, int target) {if(matrix==null || matrix.length==0 || matrix[0].length==0) return false;int l = 0;int r = matrix.length*matrix[0].length-1;int cols = matrix[0].length;while(l<=r){int m = l + ((r-l)>>1);int row = m/cols;int col = m%cols;if(matrix[row][col]==target) return true;if(matrix[row][col]>target){r = m - 1;}else{l = m + 1;}}return false;} }

也可以先在第一列查找，找到最小的比target大的元素，所在的行l(wèi)，然后在l-1行查找target是否存在。

class Solution {public boolean searchMatrix(int[][] matrix, int target) {if(matrix == null || matrix.length==0 || matrix[0].length==0) return false;int m = matrix.length;int n = matrix[0].length;//先在第一列找,l是nums[l]>target的最小值int l = 0, r = m-1;while(l<=r){int middle = l+((r-l)>>1);if(matrix[middle][0] == target) return true;if(matrix[middle][0]>target){r = middle-1;}else{l = middle+1;}}if(l>0){int line = l-1;//在line這一行查找l = 0;r = n-1;while(l<=r){int middle = l +((r-l)>>1);if(matrix[line][middle]==target) return true;if(matrix[line][middle]>target){r = middle-1;}else{l = middle+1;}}return false;}else{return false;}} }

總結(jié)

以上是生活随笔為你收集整理的74. Search a 2D Matrix的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。