题目描述

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。

样例

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true


输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false

算法1

(利用单调性) $O(n + m)$

时间复杂度

参考文献

C++ 代码

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.empty() || matrix[0].empty()) return false;
        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) j --;
            else i ++;
        }
        return false;
    }
};

算法2

(二分法) $O(log(mn))$

时间复杂度

参考文献

C++ 代码

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.empty() || matrix[0].empty()) return false;

        int l = 0, m = matrix[0].size(), n = matrix.size(), r = m * n;

        while (l < r){
            int mid = l + r >> 1;
            if (matrix[mid / m][mid % m] < target) l = mid + 1;
            else r = mid;
        }
        return matrix[r / m][r % m] == target;
    }
};


#这种情况是对二分的优化
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.empty() || matrix[0].empty()) return false;

        int l = 0, m = matrix[0].size(), n = matrix.size(), r = m * n;

        while (l < r){
            int mid = l + r >> 1;
            if (matrix[mid / m][mid % m] == target) return true;
            if (matrix[mid / m][mid % m] < target) l = mid + 1;
            else r = mid;
        }
        return false;
    }
};