【3.30】LeetCode每日一题· 搜索二维矩阵

2021年03月30日 11时51分

标签： LeetCode 数组二分

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

#### 示例1
![](https://assets.leetcode.com/uploads/2020/10/05/mat.jpg)
```
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true
```

#### 示例2
![](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/11/25/mat2.jpg)
```
输入：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
```

#### 来源
> 来源：力扣（LeetCode）
> 链接：[题目链接](https://leetcode-cn.com/problems/search-a-2d-matrix "题目链接")

## 解题思路
简单题，两次二分。
1. 首先进行**行二分**，找到最后一个**首元素小于等于`target`的行号`row`**；
2. 在该行中进行**列二分**，找到最后一个**小于等于`target`的列`col`**
3. 判断`matrix[row][col]`是否和`target`相等即可。
需要注意的是，如果`target`小于矩阵中最小的元素，`row`和`col`均为`-1`，访问数组会产生溢出，此时直接返回`false`即可。

### 代码
```cpp
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        const int M = matrix.size(), N = matrix[0].size();
        int i = 0, j = M - 1, mid, row;
        while(i <= j){
            mid = ((j - i) >> 1) + i;
            if(matrix[mid][0] > target){
                j = mid - 1;
            }else{
                i = mid + 1;
            }
        }
        row = j;
        if(row < 0) return false;
        i = 0, j = N - 1;
        while(i <= j){
            mid = ((j-i) >> 1) + i;
            if(matrix[row][mid] > target){
                j = mid - 1;
            }else{
                i = mid + 1;
            }
        }
        return j >= 0 && matrix[row][j] == target; 
    }
};
```

## 用时和内存
> 执行用时：4 ms，在所有 C++提交中击败了87.61%的用户
> 内存消耗：9.3 MB，在所有 C++提交中击败了37.85%的用户

所有评论

暂无评论

新增评论

邮箱

邮箱仅作验证使用

图形验证码

邮箱验证码

目录

【3.30】LeetCode每日一题· 搜索二维矩阵

所有评论

暂无评论

新增评论