跳转至

240 搜索二维矩阵II

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

解法一:暴力枚举

无脑解法,没有利用题意“升序”

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        for(int i = 0; i < matrix.size(); i++){
            for(int j = 0; j < matrix[i].size(); j++){
                if(matrix[i][j] == target)
                    return true;
            }
        }
        return false;
    }
};

复杂度分析

  • 时间复杂度:O(mn)。
  • 空间复杂度:O(1)。

解法二:二分查找

利用题意“升序”可直接二分查找

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

解法三:二叉搜索树

https://leetcode.cn/problems/search-a-2d-matrix-ii/solutions/2361487/240-sou-suo-er-wei-ju-zhen-iitan-xin-qin-7mtf

将矩阵逆时针旋转45度,将其变成二叉搜索树

以右上角为根节点

如果超出边界,说明无解

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

动态规划