首页 > 代码库 > LeetCode-Search a 2D Matrix II
LeetCode-Search a 2D Matrix II
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 in ascending from left to right.
- Integers in each column are sorted in ascending from top to bottom.
For example,
Consider the following matrix:
[ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30]]
Given target = 5
, return true
.
Given target = 20
, return false
.
Analysis:
String from the top right corner, if target > current value, find the row who is after current row and whose last value is less than target, we can eliminate all rows before this row (included);
if target < current value, find the col who is before the current col and whose value on current row is just less than target, we can eliminate all cols after this col (excluded).
Solution:
1 public class Solution { 2 public boolean searchMatrix(int[][] matrix, int target) { 3 if (matrix.length==0 || matrix[0].length==0) return false; 4 5 int curX = 0, curY = matrix[0].length-1; 6 while (curX!=-1 && curY!=-1){ 7 int curVal = matrix[curX][curY]; 8 if (target ==curVal) return true; 9 if (target < curVal){10 curY = searchRow(matrix,curX,curY-1,target);11 } else {12 curX = searchCol(matrix,curX+1,curY,target);13 }14 }15 return false;16 }17 18 public int searchRow(int[][] matrix, int row, int maxCol, int target){19 int start = 0, end = maxCol;20 while (start <= end){21 int mid = (end+start)/2;22 int val = matrix[row][mid];23 if (target==val) return mid;24 25 if (target > val){26 start = mid+1;27 } else {28 end = mid-1;29 }30 }31 return start-1;32 }33 34 public int searchCol(int[][] matrix, int minRow, int col, int target){35 int start = minRow, end = matrix.length-1;36 while (start <= end){37 int mid = (end+start)/2;38 int val = matrix[mid][col];39 if (target==val) return mid;40 41 if (target > val){42 start = mid+1;43 } else {44 end = mid-1;45 }46 }47 return (start==matrix.length) ? -1 : start;48 }49 }
LeetCode-Search a 2D Matrix II
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。