leetcode 240

240. 搜索二维矩阵 II - 力扣（LeetCode） (leetcode-cn.com)

题目意思比较明确，在一个行升序且列升序的二维矩阵中，查找一个数。

由于leetcode的很多题目，范围给的不是很明确。

但是很显然，这既然是一个中等难度的题目，暴力肯定是过不去的，虽然有时候leetcode的难度的标注是比较玄学的。

那我们想到了一个可以稍微简化一点的操作，那就是二分。

我想到的是，先对行考虑，二分每行的末尾元素，找到第一个大于等于target的行数。

在此行往下，对每一行进行二分操作，查找是否有与target相等的元素。

贴个代码：

class Solution {
public:

    bool binary(int m , vector a , int target)
    {
        int l = 0 ; int r = m  ; 
        while(l < r)
        {
            int mid = l + r >> 1 ;
            if(a[mid] == target)
            {
                return true ; 
            }
            else if(a[mid] > target)
            {
                r = mid ; 
            }
            else
            {
                l = mid + 1 ; 
            }
        }
        return false ; 
    }



    bool searchMatrix(vector>& matrix, int target) {
        int n = matrix.size() ; 
        int m = matrix[0].size() ; 
        int l = 0 ;  int r = n -1 ; 
        while(l < r)
        {
            int mid = l + r >> 1 ; 
            if(matrix[mid][m-1] >= target)
            {
                r = mid ; 
            }
            else
            {
                l = mid + 1 ; 
            }
        }

        for(int i = l ; i < n  ; ++ i)
        {
            if(binary(m , matrix[i] , target))
            {
                return true ; 
            }
        }
        return false ; 
    }
};

但是情况不是很乐观，时间只打败了5%……

最后翻阅题解，找到了一种很容易理解，而且时间更短的做法。

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

其实就是有点像z字抖动。起点是从左下角开始，如果遇到的值比target小 ， 就往右走，反之，就往上走。

是好方法，mark一下，等之后，遇到了扩展问题希望可以想起来。