LeetCode74. 搜索二维矩阵

比眉伴天荒 2022-11-15 03:42 158阅读 0赞

难度：`中等`  
题目描述：

> 编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
> 
> 每行中的整数从左到右按升序排列。  
> 每行的第一个整数大于前一行的最后一个整数。

示例 1：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoYW9rdWRlenR0_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][20210330195918422.png]  
解题思路：

> 从左下角开始遍历，如果当前元素值比target大的话就向上走，否则向右走

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

或者用二分：

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoYW9rdWRlenR0_size_16_color_FFFFFF_t_70]: /images/20221022/927ef15ed57a42a9921a6bb06dd4a780.png
[20210330195918422.png]: https://img-blog.csdnimg.cn/20210330195918422.png