目录

Leetcode240:搜索二维矩阵——二分、矩阵

题目

https://leetcode-cn.com/problems/search-a-2d-matrix-ii/

题解

法一:逐行二分

没啥好说的,代码可以参考一下

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        for (const auto& row: matrix) {
            auto it = lower_bound(row.begin(), row.end(), target);
            if (it != row.end() && *it == target) {
                return true;
            }
        }
        return false;
    }
};

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/search-a-2d-matrix-ii/solution/sou-suo-er-wei-ju-zhen-ii-by-leetcode-so-9hcx/
来源:力扣(LeetCode
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

对一行使用二分查找时间复杂度O(logm),对n行使用二分查找时间复杂度O(nlogm)。

法二:巧妙的利用性质

观察矩阵最右上角的元素:

  • 它是所在行最大的元素
  • 它是所在列最小的元素

这就有点像二分法了。对于一个目标数target,如果target<matrix[row][col],则target一定不在第col列。如果target>matrix[row][col],则它一定不在第row行。

所以我们只要判断targetmatrix[row][col]的大小,就能排除某一行或某一列的所有元素。

上代码:

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int row = 0;
        int col = matrix[0].size()-1;
        while(row<matrix.size() && col>=0){
            if(target < matrix[row][col]){
                col--;
            }else if(target > matrix[row][col]){
                row++;
            }else{
                return true;
            }
        }
    return false;

    }
};

最多把所有的行和列都排除一遍,时间复杂度只有O(m+n)。这个方法很巧妙!

其实关注左下角的元素也是一样的:

  • 它是所在行最小的元素
  • 它是所在列最大的元素

明白了就不觉得难了。