中等 · 矩阵 · 原题

题目信息

LeetCode #240 · Search a 2D Matrix II

标签：数组、二分查找、分治、矩阵

题目要求

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

  • 每行的元素从左到右升序排列。

  • 每列的元素从上到下升序排列。

示例 1：

1
2
输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出：true

示例 2：

1
2
输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
输出：false

提示：

  • m == matrix.length

  • n == matrix[i].length

  • 1 <= n, m <= 300

  • -10^9 <= matrix[i][j] <= 10^9

  • 每行的所有元素从左到右升序排列

  • 每列的所有元素从上到下升序排列

  • -10^9 <= target <= 10^9

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        for(int i=0;i<matrix.size();i++){
            int l=0,r=matrix[i].size()-1,mid=(l+r)>>1;
            while(l<r){
                mid=(l+r)>>1;
                if(matrix[i][mid]==target) return true;
                else if(matrix[i][mid]<target) l=mid+1;
                else r=mid-1;
            }
            if(matrix[i][l]==target) return true;
        }
        return false;
    }
};

返回目录