当前位置：网站首页>LeetCode 74、搜索二维矩阵

LeetCode 74、搜索二维矩阵

2022-04-23 20:23:00 【亡于灬】

74、搜索二维矩阵

1）题目描述

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

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

示例 1：

img

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

示例 2：

img

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

提示：

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 100
  • -10^4 <= matrix[i][j], target <= 10^4

2）分析

行遍历，行内二分。

  • 由题可知，按照行先遍历矩阵，矩阵元素是非递减的。那么如果目标值小于矩阵行先遍历第一个元素或者大于最后一个元素，目标值一定不再矩阵中；
  • 若目标值可能在矩阵中，则遍历矩阵每一行，将目标值与当前行的最后一个元素比较，判断目标值是否可能在当前行中；
  • 若目标值在当前行中，通过二分法搜索对应的元素的下标；
  • 判断搜索到的下标对应的元素与目标值是否相等。

3）C++代码

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

版权声明
本文为[亡于灬]所创，转载请带上原文链接，感谢
https://blog.csdn.net/qq_38342510/article/details/124360319

边栏推荐

猜你喜欢

随机推荐