剑指 Offer 04. 二维数组中的查找

超、凢脫俗 2023-01-12 04:20 114阅读 0赞

题目描述：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgxMjYwOQ_size_16_color_FFFFFF_t_70]  
将二维数组逆时针旋转45°，可以将整个矩阵看作一个二叉搜索树，其中右上角和左下角可分别看作根节点。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgxMjYwOQ_size_16_color_FFFFFF_t_70 1]  
左下角看作根节点：若当前值大于target则舍弃该行，若当前值小于target则舍弃该列。

class Solution { 
        public boolean findNumberIn2DArray(int[][] matrix, int target) { 
            int rows = matrix.length - 1;
            if(rows < 0){ 
                return false;
            }
            int columns = matrix[0].length;
            int j = 0;
            while(rows >= 0 &&j < columns){ 
                if(matrix[rows][j] > target){ 
                    rows--;
                }else if(matrix[rows][j] < target){ 
                    j++;
                }else{ 
                    return true;
                }
            }
            return false;
        }
    }

右上角看作根节点：若target大于本节点则舍弃该行进入下一行，若小于target则舍弃该列进入前一列

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgxMjYwOQ_size_16_color_FFFFFF_t_70]: /images/20221119/ecf4994998db44fa8676ae95056fcab3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgxMjYwOQ_size_16_color_FFFFFF_t_70 1]: /images/20221119/2bcead62e74243ce9a572f84ec51be7d.png