解搜索二维矩阵题
今天我来讲下我做这道题的思路吧。原题点击此处跳转 。
下面是具体的题目:
编写一个高效的算法来搜索 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。
看似很平常的题，逐行搜索也可以解决，但是题目中要求使用高效的算法，所以本题的解题思路肯定是不是两层for循环那么简单。
结合题目描述二维矩阵有『从左往右，上往下是递增』的规律，可以摸索出，我们只要横着扫一行，竖着扫一列，便可以大致确定范围，例如题目中的target = 5，在第一行中小于等于5的只有1，4两个数，在第一列中小于五的数只有1，2，3三个数，那么搜索的范围就可以确定为 一个2*3的矩阵。相比5*5是不是范围小了很多。
但是！
这就是最高效的算法吗？接下来我们算示例中给的第二个target=20, 我们发现第一行全都小于20，第一列全都小于20，看来还是要遍历整个矩阵了。所以上面那种思路并不能算是高效的（因此便不放代码）。那么对于target=20这种输入，该如何优化呢？
我们再来抠题目中的『从左往右，上往下是递增』的规律，那么我们一开始搜索每行最右边的数字，判定他与目标值的关系，假如最右边的值小于目标值，根据题目中的规律，这一行都不用搜索了，肯定比目标值小。假如最右边的值大于目标值，我们便向右边搜索，因为往下搜索已经是永远大于目标值了。根据这个条件我们对于target=20的搜索路径为15->19->22->24->30->26->23->21->18，只需要搜索9次，便可以给出答案。是不是比搜索25个值快多了。同样对于target=5的输入，我们的搜索路径为15->11->7->4->5，也不用像前面提到的搜索行与列确定范围那么麻烦。
下面是我写的代码
bool Solution::searchMatrix(std::vector<std::vector<int>> &matrix, int target) {
if (matrix.size() == 0 || matrix[0].size() == 0 || matrix[0][0] > target ||
matrix[matrix.size() - 1][matrix[0].size() - 1] < target) {
return false;
}
int h = matrix.size();// i
int w = matrix[0].size(); // j
int i = 0, j = 0;
// int l = 0;
for (i = 0; i < h; i++) {
if (matrix[i][w - 1] < target) {
// std::cout << w-1 << ",-" << i <<"," <<l<<std::endl;
// ++l;
continue;
}
for (j = w - 1; j >= 0; j--) {
// std::cout << j << ",-" << i << "," << l << std::endl;
// ++l;
if (matrix[i][j] == target) {
return true;
} else if (matrix[i][j] < target) {
break;
} else {
w = j;
}
}
}
return false;
}
}
注释的l变量是用来打印搜索路径的。
我们看下搜索路径图(原点是第一个元素，矩阵向右，和向下延伸)
测试无误之后，提交。然后再去看大神的代码。然后发现我和大神代码之间差了好几个卧槽。
bool Solution::searchMatrix(std::vector<std::vector<int>> &matrix, int target) {
// int l = 0;
int n = matrix.size();
if (n == 0)
return false;
int m = matrix[0].size();
for (int c = 0, r = m - 1; c < n && r >= 0;) {
// std::cout << "" << r << ",-" << c << "," << l << std::endl;
// ++l;
if (matrix[c][r] > target) {
--r;
} else if (matrix[c][r] < target) {
++c;
} else
return true;
}
return false;
}
因为思路是一样，所以搜索路径是一样的，这里就不放图了。但是代码要精简很多，值得学习。