- 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.
Consider the following matrix:
[ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ]Given target =
3
, return true
.
Solution: consider the matrix as a one-dimensional array, and then do binary search.
class Solution { public: bool searchMatrix(vector<vector<int> > &matrix, int target) { // Start typing your C/C++ solution below // DO NOT write int main() function if(matrix.empty() || matrix[0].empty()) return false; int cols = matrix[0].size(); int start = 0, end = matrix.size()*cols-1; while(start<=end){ int middle = (start+end)/2; if(matrix[middle/cols][middle%cols]==target) return true; if(matrix[middle/cols][middle%cols]<target) start = middle+1; else end = middle-1; } return false; } };
No comments:
Post a Comment