题目描述
题目链接:240. Search a 2D Matrix II
Write an efficient algorithm that searches for a
target
value in anm x n
integermatrix
. Thematrix
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.
例子
例子 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
例子 2
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 = 20
Output:false
Follow Up
Note
Constraints
m == matrix.length
n == matrix[i].length
1 <= n, m <= 300
-10^9 <= matix[i][j] <= 10^9
All the integers in each row are sorted in ascending order.
All the integers in each column are sorted in ascending order.
-10^9 <= target <= 10^9
解题思路
[Leetcode]74. Search a 2D Matrix(C++) 的变种版本,这次给定矩阵符合条件是,每一行同样是已排序,但每一行不一定所有元素都比上一行大,只满足每一列是升序。也就是我们在上一题中用过的二分查找锁定某一行的方法不可行了,因为可能有多行满足第一个元素比target 小,最后一个元素比 target 大的条件。因此我们需要对每一行进行一次二分查找,不过可以利用每一列也是升序的特点,对每行行首和行尾分别进行一次二分查找,筛掉所有元素都大于/小于 target 的行,对剩余行进行二查找即可。代码如下:
#include <vector>
class Solution {
public:
bool searchMatrix(std::vector<std::vector<int>>& matrix, int target) {
int m = matrix.size();
int n = matrix[0].size();
std::pair<int, int> valid_range{0, m - 1};
int left = 0;
int right = m - 1;
// filter out rows where all elements are larger than target
while (left < right) {
int mid = (left + right) / 2 + 1;
if (matrix[mid][0] > target) {
right = mid - 1;
valid_range.second = right;
} else if (matrix[mid][0] < target) {
left = mid;
} else {
return true;
}
}
// filter out rows where all elements are smaller than target
left = 0;
while (left < right) {
int mid = (left + right) / 2;
if (matrix[mid][n - 1] < target) {
left = mid + 1;
valid_range.first = left;
} else if (matrix[mid][n - 1] > target) {
right = mid;
} else {
return true;
}
}
// for the rest rows, do a binary search for each row
for (int r = valid_range.first; r <= valid_range.second; ++r) {
left = 0;
right = n - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (matrix[r][mid] < target) {
left = mid + 1;
} else if (matrix[r][mid] > target) {
right = mid - 1;
} else {
return true;
}
}
}
return false;
}
};
- 时间复杂度:
O(mlog n)
– 由于有剪枝,实际复杂度会更小一点 - 空间复杂度:
O(1)
GitHub 代码同步地址: 240.SearchA2DMatrixIi.cpp
其他题目: GitHub: Leetcode-C++-Solution 博客: Leetcode-Solutions