题解 |【动图画解】 #二维数组中的查找# 跟二叉搜索很像 进来看哦
默认你已读懂题意了哈
绅士们多看点，延年益寿哦😜
我的解题思路如下
假如你用暴力法遍历矩阵 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;
}
}
