典型老题,从右上角开始搜索,往下是增往左是减。
比如.
[[1 4],
[2 5]]
右上角元素即4
ir是行标,ic是列标
假设target是2, target < 4, ic--
target > 1, ir++
target == 2,找到
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int n_row = matrix.size();
if (n_row == 0)
return false;
int n_col = matrix[0].size();
if (n_col == 0)
return false;
int i = 0;
int j = n_col - 1;
while (0 <= i && i < n_row && 0 <= j && j < n_col) {
if (target == matrix[i][j])
return true;
else if (target < matrix[i][j])
j--;
else
i++;
}
return false;
}
};
网友评论