mirror of
https://github.com/ShusenTang/LeetCode.git
synced 2024-09-02 14:20:01 +00:00
40 lines
2.0 KiB
Markdown
40 lines
2.0 KiB
Markdown
# [240. Search a 2D Matrix II](https://leetcode.com/problems/search-a-2d-matrix-ii/)
|
||
|
||
# 思路
|
||
在一个二维矩阵中查找，二维矩阵满足从左到右、从上到下递增有序。
|
||
|
||
由于我们对一维有序数组查找很熟悉，即使用二分法，所以此题很容易陷入死胡同——寻找到复杂度为`log(m) + log(n)`的算法，其中m和n为高宽。
|
||
但其实是找不到的，详见[讨论](https://leetcode.com/problems/search-a-2d-matrix-ii/discuss/66154/Is-there's-a-O(log(m)%2Blog(n))-solution-I-know-O(n%2Bm)-and-O(m*log(n)))。
|
||
|
||
此题最简单也是（一般情况下）最优的解法是**马鞍搜索法**：
|
||
1. 从数组的左下角（或右上角，类似的）开始搜索;
|
||
2. 如果目标数值比当前值小，那么它如果在数组存在一定在当前值上方，向上移动一个元素;
|
||
3. 如果目标数值比当前值大，那么它如果在数组存在一定在当前值右面，向右移动一个元素;
|
||
4. 回到第二步，再次开始搜索直到找到或者超出边界。
|
||
|
||
时间复杂度O(m+n)。
|
||
|
||
> 当m或者n很小（甚至为1）时二维矩阵退化成一维，此时线性复杂度就显得有点高了，针对此种特殊情况，Richard S. Bird对其[做出了相关改进](http://www.cs.ox.ac.uk/publications/publication2664-abstract.html)，
|
||
关于此题更详细的分析见[此处](https://stackoverflow.com/questions/2457792/how-do-i-search-for-a-number-in-a-2d-array-sorted-left-to-right-and-top-to-botto/2458113#2458113)。
|
||
|
||
# C++
|
||
``` C++
|
||
class Solution {
|
||
public:
|
||
bool searchMatrix(vector<vector<int> > &matrix, int target) {
|
||
if (matrix.empty() || matrix[0].empty()) return false;
|
||
|
||
int m = matrix.size(), n = matrix[0].size();
|
||
// if (target < matrix[0][0] || target > matrix[m-1][n-1]) return false;
|
||
|
||
int x = m - 1, y = 0;
|
||
while (x >= 0 && y < n) {
|
||
if (matrix[x][y] > target) --x;
|
||
else if (matrix[x][y] < target) ++y;
|
||
else return true;
|
||
}
|
||
return false;
|
||
}
|
||
};
|
||
```
|