解搜索二维矩阵题

今天我来讲下我做这道题的思路吧。原题点击此处跳转。

下面是具体的题目:

编写一个高效的算法来搜索 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三个数，那么搜索的范围就可以确定为一个23的矩阵。相比55是不是范围小了很多。

但是！

这就是最高效的算法吗？接下来我们算示例中给的第二个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，也不用像前面提到的搜索行与列确定范围那么麻烦。

下面是我写的代码

<br />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;
}

因为思路是一样，所以搜索路径是一样的，这里就不放图了。但是代码要精简很多，值得学习。

评论