Search a 2D Matrix II
这个solution复杂度为O(row + column)
主要思想是从右上角开始搜索，行列元素值递增，所以当前元素小于target时，target会出现在当前行下方，当当前元素大于target时，target谁出现在当前列左侧。
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if (matrix.empty() || matrix[0].empty()) return false;
int row(matrix.size()), column(matrix[0].size());
int i(0), j(column - 1);
while (i < row && j >= 0) {
if (matrix[i][j] == target) return true;
if (matrix[i][j] < target) i++;
else j--;
}
return false;
}
};
网友评论