首页 > 代码库 > 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.
思路：将矩阵看做行优先的有序数组，直接使用二分查找即可。
1 class Solution { 2 public: 3 bool searchMatrix( vector<vector<int>> &matrix, int target ) { 4 if( matrix.empty() ) { return false; } 5 int rows = matrix.size(), cols = matrix[0].size(); 6 int start = 0, end = rows*cols-1; 7 while( start <= end ) { 8 int middle = ( start + end ) / 2; 9 if( matrix[middle/cols][middle%cols] < target ) {10 start = middle + 1;11 } else if( matrix[middle/cols][middle%cols] > target ) {12 end = middle - 1;13 } else {14 return true;15 }16 }17 return false;18 }19 };
每次选取矩阵右上角的元素与target进行比较：若matrix[0][cols-1]<target，则可排除第cols-1列；若matrix[0][cols-1]>target，则可排除第0行。
1 class Solution { 2 public: 3 bool searchMatrix( vector<vector<int>> &matrix, int target ) { 4 if( matrix.empty() ) { return false; } 5 int rows = matrix.size(), cols = matrix[0].size(); 6 int i = 0, j = cols - 1; 7 while( i < rows && j >= 0 ) { 8 if( matrix[i][j] == target ) { return true; } 9 if( matrix[i][j] < target ) {10 ++i;11 } else {12 --j;13 }14 }15 return false;16 }17 };
Search a 2D Matrix
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。