1.解答之前的碎碎念:
这个题一开始我想的很简单,想着是个二维的二分查找,然后提交代码,果不其然出错了。。。因为并不能保证第i+1行的每个元素都大于第i行,不过想到了递归,也算是有点进步(虽然最后用递归写了一个没有通过。。。但是自己在vs里测试的没问题呀。。。不明白为什么)。
2.问题描述:
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性:
- 每行的元素从左到右升序排列。
- 每列的元素从上到下升序排列。
示例:
现有矩阵 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
,返回 true
。
给定 target = 20
,返回 false
。
3.解答思路:
参考链接:https://blog.csdn.net/majichen95/article/details/81632067
摘录:
如果我们观察题目中给的那个例子,我们可以发现有两个位置的数字很有特点,左下角和右上角的数。例如右上角的7,往左所有的数变小,往下所有数增加,那么我们就可以和目标数相比较,如果目标数大,就往下搜,如果目标数小,就往左搜。这样就可以判断目标数是否存在。
4.答案:
注意:要考虑矩阵为空的情况!
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if (matrix.empty())
{
return false;
}
int m = matrix.size();
int n = matrix[0].size();
int x = 0;
int y = n - 1;
while (x < m && y >= 0)
{
if(x == m - 1 && y == 0)
{
if (target == matrix[x][y])
{
return true;
}
else return false;
}
else
{
if (target == matrix[x][y])
{
return true;
}
else if (target < matrix[x][y])
{
--y;
}
else
{
++x;
}
}
}
return false;
}
};