首页 > 代码库 > Leetcode-Search a 2D Matrix
Leetcode-Search a 2D Matrix
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
- Integers in each row are sorted from left to right.
- The first integer of each row is greater than the last integer of the previous row.
For example,
Consider the following matrix:
[ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50]]
Given target = 3, return true.
写得蛮啰嗦，简而言之就是先搜索列号，再在搜索到的列里面去搜索该元素，全部用的二分查找（反正它已经排序了）
1 public boolean searchMatrix(int[][] matrix, int target) { 2 if(matrix==null||matrix.length <=0){ 3 return false; 4 } 5 int targetRow =0; 6 int m = matrix.length; 7 int n = matrix[0].length; 8 9 //make sure target is in the range10 if(target < matrix[0][0] || target > matrix[m-1][n-1]){11 return false;12 }else{13 targetRow = searchRow(matrix,target,0,m-1);14 if(targetRow == -1){15 return false;16 }17 return searchElement(matrix,target,targetRow,0,n-1);18 }19 20 }21 public int searchRow(int[][] matrix,int target,int start,int end){22 while(start <= end){23 int mid = (end-start)/2 +start;24 if(matrix[mid][0] == target){25 return mid;26 }27 if(matrix[mid][0] < target){28 if(matrix[mid][matrix[0].length -1] >= target){29 return mid;30 }else{31 start = mid +1;32 continue;33 }34 }35 if(matrix[mid][0] > target){36 end = mid-1;37 continue;38 }39 40 }41 return -1;42 }43 44 public boolean searchElement(int [][] matrix,int target,int row,int start,int end){45 while(start <= end){46 int mid = (end-start)/2 + start; 47 if( matrix[row][mid] == target){48 return true;49 }50 if(matrix[row][mid] < target){51 start = mid+1;52 continue;53 }54 if(matrix[row][mid] > target){55 end = mid - 1;56 continue;57 }58 }59 return false;60 }
Leetcode-Search a 2D Matrix
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。