解题思路

由于矩阵的行元素和列元素都是有序的，从左到右递增，从上到下递增，完全递增元素不会有重复。则可以找到规律：

• 左上为最小值；
• 右下为最大值；
• 左下元素大于它上方的元素，小于它右方的元素；
• 右上元素大于它左方的元素，小于它下方的元素。

具体步骤：

• 获取矩阵的行和列长，处理特殊情况。
• 以左下角为起点，如果它小于target，则将往右移动，即当前列加一；如果它大于target，则将往上移动，即当前行减一；
• 如果移动到了矩阵边界也没找到，说明矩阵中不存在目标值。

复杂度：

• 时间复杂度为O（m+n），空间复杂度为O（1）。

class Solution:
    def Find(self , target: int, array: List[List[int]]) -> bool:
        # write code here
        # 先纵向二分
        n = len(array)
        m = len(array[0])
        if n == 0 or m ==0:
            return False

        i = 0
        j = n-1
        while i < m and j >=0:
            if array[j][i] < target:
                i += 1
            elif array[j][i] > target:
                j -= 1
            else:
                return True

        return False

2023年9月5日再刷

从左下角开始遍历，如果target大于当前值，往右移一位；如果target小于当前值，往上移一位；如果target等于当前值，返回True。遍历完成之后还没有找到，就返回False。

C++

class Solution {
public:
    bool Find(int target, vector<vector<int> >& array) {
        int i = array.size()-1;
        int j = 0;

        while(i >= 0 && j < array[0].size())
        {
            if(target > array[i][j]) j++;
            else if(target < array[i][j]) i--;
            else return true;
        }

        return false;
    }
};

Python

class Solution:
    def Find(self , target: int, array: List[List[int]]) -> bool:
        i = len(array)-1
        j = 0

        while i >= 0 and j < len(array[0]):
            if target > array[i][j]:
                j += 1
            elif target < array[i][j]:
                i -= 1
            else:
                return True

        return False