首页 > 代码库 > leetcode 74 Search a 2D Matrix ----- java
leetcode 74 Search a 2D Matrix ----- java
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.
题目意思就是给定一个矩阵，按照从小到达排列，然后给定一个数字，判断数字是否在矩阵中。
就是用二分法的应用。两种方法，第一种稍微慢一些。
第一种是用了两次二分法，先找出行数、再在这一行上找具体是否存在。
第二种是直接应用二分法，效率更高。
public class Solution { public boolean searchMatrix(int[][] matrix, int target) { int len1 = matrix.length; if( len1 == 0 ) return false; int len2 = matrix[0].length; if( len2 == 0 || target < matrix[0][0]) return false; int row_start = 0,row_end = len1-1; int col_start = 0,col_end = len2-1; int row = (row_end+row_start)/2 ,col; while( row_start <= row_end){ row = (row_end+row_start)/2; if( target >= matrix[row][0] ){ if( row == len1-1 || target < matrix[row+1][0]) break; else row_start = row+1; } else{ if( row == 0 || target >= matrix[row-1][0]){ row--; break; } else row_end = row-1; } } while( col_start <= col_end){ col = (col_end+col_start)/2; if( target > matrix[row][col] ){ if( col == col_end ) return false; else col_start = col+1; }else if( target < matrix[row][col] ){ if (col == col_start) return false; else col_end = col-1; }else return true; } return false; }}
public class Solution { public boolean searchMatrix(int[][] matrix, int target) { int len1 = matrix.length; if( len1 == 0 ) return false; int len2 = matrix[0].length; if( len2 == 0 || target < matrix[0][0]) return false; int start = 0,end = len1*len2-1,flag ; while( start <= end ){ flag = (start+end)/2; int num = matrix[flag/len2][flag%len2]; if( target > num) start = flag+1; else if ( target < num) end = flag-1; else return true; } return false; }}
leetcode 74 Search a 2D Matrix ----- java
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。