首页 > 代码库 > [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.
Solution 1:
public class Solution { public boolean searchMatrix(int[][] matrix, int target) { int N=matrix.length-1; int M=matrix[0].length-1; int i=0; int j=M; while(j>=0&&i<=N){ if(matrix[i][j]==target){ return true; }else if(matrix[i][j]<target){ ++i; }else{ --j; } } return false; }}
Solution 2:
2分法。
1 public class Solution { 2 public boolean searchMatrix(int[][] matrix, int target) { 3 int min=0; 4 int max=matrix[0].length*matrix.length-1; 5 while(min<=max){ 6 int mid=(min+max)/2; 7 int y=mid/matrix[0].length; 8 int x=mid%matrix[0].length; 9 if(matrix[y][x]==target)10 return true;11 else if(matrix[y][x]>target){12 max=mid-1;13 }else{14 min=mid+1;15 }16 }17 return false;18 }19 }
[Leetcode] Search a 2D Matrix
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。