剑指 Offer 04-二维数组中的查找c++

题目描述

解法 递增查找法

之前刚好做过LeetCode的第一题<两数之和>，发现本质上的是同一个题目,这题可以说是它的简化版本，leetcode-01-两数之和，思路就不再赘述了。

class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        int i=matrix.size()-1,j=0;
        while(i >= 0 && j < matrix[0].size())
        {
            if(matrix[i][j]>target) i--;
            else if(matrix[i][j]<target) j++;
            else return true;
        }
        return false;
    }
};

时间复杂度O(M+N)
最差情况从 i = matrix.size()-1,j = 0;到i = matrix.size()-1,j = matrix.size()-1,
再从 i = maxtrix.size()-1,j = matri.size()-1到 **i = 0, j = matrix.size()-1;**刚好M+N次
空间复杂度 O(1)