leetcode-74：搜索二维矩阵题目解题

题目

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

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

示例 1：

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

示例 2：

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

解题

方法一：二分查找 （二维转化为一维）

可以将二维展开成一维，然后就可以使用二分查找了

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

方法二：

从右上角出发，可以看成二叉搜索树

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

最后

以上就是淡然往事为你收集整理的leetcode-74：搜索二维矩阵题目解题的全部内容，希望文章能够帮你解决leetcode-74：搜索二维矩阵题目解题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。