剑指Offer04.二维数组中的查找(BST)

原题链接

思路:这题乍看上去好像是一个二分,其实上有更优的解法,由于从右上角往左下角看刚好是一颗二叉搜索树的形状,因此可以把这个二维数组看作是一个BST,因此解法就是BST的查找功能在此数组中的实现,将右上角元素看为根节点,从根节点开始,如果当前元素小于目标元素则找他的左子树,大于则找他右子树,否则就说明找到了,如果一直到数组越界都没有找到说明BST中不存在这个数。

参考代码

剑指Offer04.二维数组中的查找(BST)
 1 public boolean findNumberIn2DArray(int[][] matrix, int target) {
 2         int maxY = matrix.length;
 3         int maxX = 0;
 4         if(maxY > 0) {
 5             maxX = matrix[0].length;
 6         }
 7         boolean flag = false;
 8         int x = maxX - 1, y = 0;
 9         while(x >= 0 && y < maxY) {
10             if(matrix[y][x] > target) {
11                 x --;
12             } else if(matrix[y][x] < target) {
13                 y ++;
14             } else {
15                 flag = true;
16                 break;
17             }
18         }
19         return flag;
20     }
View Code

 

上一篇:[HNOI2003]激光炸弹(二维前缀和+大坑点)


下一篇:leetcode-每日一题2021.11.16 完美矩形