【一天一道LeetCode】#74. Search a 2D Matrix

发布时间：2020-12-13 21:08:19 所属栏目：PHP教程来源：网络整理

导读：1天1道LeetCode 本系列文章已全部上传至我的github，地址：ZeeCoder‘s Github 欢迎大家关注我的新浪微博，我的新浪微博欢迎转载，转载请注明出处（1）题目 Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has

1天1道LeetCode

本系列文章已全部上传至我的github，地址：ZeeCoder‘s Github
欢迎大家关注我的新浪微博，我的新浪微博
欢迎转载，转载请注明出处

（1）题目

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted from left to right.

The first integer of each row is greater than the last integer of the previous row.

For example,

Consider the following matrix:

[
[1,3,5,7],
[10,11,16,20],
[23,30,34,50]
]

Given target = 3,return true.

（2）解题

剑指offer上的老题了，矩阵是排好序的，那末我们可以从其中找到规律。
从右上角(0，n)开始扫描，如果target比它大就往下找，如果小就往左侧找。
具体看代码：

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix,int target) {
        if(matrix.size()==0) return false;
        int i = matrix.size()-1;
        int j = 0;
        while(i>=0 && j< matrix[0].size())
        {
            if(target==matrix[i][j]) return true;//找到
            if(target>matrix[i][j]) j++;//如果target大，就往下找
            else i--;//反之则往左找
        }
        return false;
    }
};

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!