LeetCode 74. 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.
Example 1:
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true
method: 二分
注意二维下标的查找方式
通过一维下标除以列数、模以列数索引二维矩阵
0 1 2 3
4 5 6 7
8 9 10 11
一维下标9对应的二维下标是:[9 / 4][9 % 4] = [2][1]
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int n = matrix.size(), m = matrix[0].size();
int l = 0, r = n * m - 1;
while (l < r) {
int mid = l + r >> 1;
if (matrix[mid / m][mid % m] >= target) r = mid;
else l = mid + 1;
}
return matrix[r / m][r % m] == target;
}
时间复杂度:$O(log(mn))$
空间复杂度:$O(1)$
LeetCode 240. Search a 2D Matrix II
Write an efficient algorithm that searches for a target value in an m x n
integer matrix. The matrix has the following properties:
Integers in each row are sorted in ascending from left to right
.
Integers in each column are sorted in ascending from top to bottom
.
Example 1:
Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
Output: true
method: 单调性扫描(Z字形查找)
从右上角看,左边的数都比它小,下边的数都比它大
如果大于target
,就往左移
如果小于target
,就往下移
时间复杂度:$O(n + m)$
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m = matrix.size(), n = matrix[0].size();
int l = 0, r = n - 1;
while (l < m && r >= 0) {
if (matrix[l][r] < target) l++; // 小了就往下移
else if (matrix[l][r] > target) r--; // 大了就往左移
else return true;
}
return false;
}
时间复杂度:$O(m+n)$,l
最多移动m
次,r
最多移动n
次