题解 |【动图画解】 #二维数组中的查找# 跟二叉搜索很像 进来看哦

默认你已读懂题意了哈

绅士们多看点，延年益寿哦😜

我的解题思路如下

假如你用暴力法遍历矩阵 matrix ，那么它的时间复杂度是 O(N)。但是暴力法没有用矩阵 “从上到下递增、从左到右递增” 的特点，显然这不是我们想要的最优解法啦。

你看下面图，我们把矩阵逆时针旋转 45°，然后把矩阵转化成图的形式，发现它的形状跟二叉搜索树很类似，为啥？因为每个元素，跟它的左分支元素更小、右分支元素更大。所以，通过 “根节点” 开始搜索，遇到比 target 大的元素就向左，反之向右走，我们就能找到目标值 target啦。 “根节点” 对应的是上面图中矩阵的 “左下角” 和 “右上角” 元素，在这里我们把根节点称之为 标志数，以 matrix的左下角元素 令为标志数 flag，则:

• 若 flag > target，则 target 一定在 flag 所在行的上方 ，即 flag 所在行可以被消去。
• 若 flag < target，则 target 一定在 flag 所在列的右方，即 flag 所在列可以被消去。

流程如下

从矩阵 matrix 左下角元素（索引设为 (i, j)）开始遍历，并与目标值进行对比：

• 当 matrix[i][j] > target 时，执行 i-- ，即消去第 i 行元素；
• 当 matrix[i][j] < target 时，执行 j++ ，即消去第 j 列元素；
• 当 matrix[i][j] = target 时，返回 true，代表已找到目标值。

若行索引或列索引越界了，则代表矩阵中没有目标值，返回 false 即可；

那么每轮 i 或 j 移动后，等价都会生成了“消去一行（列）的新矩阵”， 并且 索引(i,j) 会指向新矩阵的左下角元素（标志数），所以可重复使用上面的性质来消去行和列，这个不就省事很多了嘛。

复杂度分析下

• 时间复杂度是 O(M+N)：其中，N 和 M 分别作为矩阵行数和列数，那么算法最多循环 M+N 次。
• 空间复杂度是 O(1): 其中i, j指针使用常数大小的额外空间。

代码如下

//Java这样来写
class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        int i = matrix.length - 1, j = 0;
        while(i >= 0 && j < matrix[0].length)
        {
            if(matrix[i][j] > target) i--;
            else if(matrix[i][j] < target) j++;
            else return true;
        }
        return false;
    }
}