首页 > 代码库 > LeetCode: Search a 2D Matrix 解题报告
LeetCode: Search a 2D Matrix 解题报告
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:
采用经典的二分法模板
1 while (left <= right) { 2 int mid = left + (right - left) / 2; 3 4 5 int n = matrix[row][col]; 6 7 if (n == target) { 8 ... 9 } else if (n < target) {10 left = mid + 1;11 } else {12 right = mid - 1;13 }14 }
1 public class Solution { 2 public boolean searchMatrix(int[][] matrix, int target) { 3 if (matrix == null || matrix.length == 0 || matrix[0].length == 0) { 4 return false; 5 } 6 7 int rows = matrix.length; 8 int cols = matrix[0].length; 9 10 int num = rows * cols;11 12 int left = 0;13 int right = num - 1;14 15 while (left <= right) {16 int mid = left + (right - left) / 2;17 18 int row = mid / cols;19 int col = mid % cols;20 21 int n = matrix[row][col];22 23 if (n == target) {24 return true;25 } else if (n < target) {26 left = mid + 1;27 } else {28 right = mid - 1;29 }30 }31 32 return false; 33 }34 }
GITHUB:
https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/divide2/SearchMatrix.java
LeetCode: Search a 2D Matrix 解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。