首页 > 代码库 > 74. Search a 2D Matrix
74. 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.
思路：从top开始比较每一行的最后一个数，如果大于target，那么就在这一行。然后用binary search即可。
public class Solution { public boolean searchMatrix(int[][] matrix, int target) { int h=matrix.length-1; int l=matrix[0].length-1; int i=0; while(i<=h) { if(matrix[i][l]>=target) { int low=0; int high=matrix[0].length-1; while(low<=high) { int mid=low+(high-low)/2; if(matrix[i][mid]==target) { return true; } else if(matrix[i][mid]<target) { low=mid+1; } else { high=mid-1; } } return false; } i++; } return false; }}
Solution2:
discussion有种非常好的解法，相当于把matrix摊开，当作1d array来做。
长度=Row*Col
Index= matrix[mid/col][mid/row]
1 2 3 4－ ［2/4］［2%4］
public class Solution { public boolean searchMatrix(int[][] matrix, int target) { int row=matrix.length,col=matrix[0].length; int l=0,r=row*col-1; while(l<=r){ int mid=(r+l)/2; if(matrix[mid/col][mid%col]==target){ return true; }else if(matrix[mid/col][mid%col]<target){ l=mid+1; }else{ r=mid-1; } } return false; }}
74. Search a 2D Matrix
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。