搜索二维矩阵Ⅱ [leetcode] --java实现

矫情吗；* 2022-03-10 08:54 183阅读 0赞

### 题目描述： ###

编写一个高效的算法来搜索 *m* x *n* 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：

*  每行的元素从左到右升序排列。
 *  每列的元素从上到下升序排列。

**示例:**

现有矩阵 matrix 如下：

[
      [1,   4,  7, 11, 15],
      [2,   5,  8, 12, 19],
      [3,   6,  9, 16, 22],
      [10, 13, 14, 17, 24],
      [18, 21, 23, 26, 30]
    ]

给定 target = `5`，返回 `true`。

给定 target = `20`，返回 `false`。

### 分析： ###

根据题目的条件 每一行元素是从左到右升序，每一列从上到下升序，所以左上角的元素是最小的，右下角的元素是最大的，当给定的target小于左上角或者大于右下角的元素时即不可能在矩阵里，直接返回false就行了。

### 思路： ###

搜索矩阵的几个题类似，可以将左下角元素当作标尺，当target大于这个元素的时候，则可能存在于这行的后面，当target小于这个元素的时候则向上移动一行再进行比较，找到目标元素直接返回true，当找完最上面一行的时候没有找到target则返回false

### 代码： ###

class Solution {
        public boolean searchMatrix(int[][] matrix, int target) {
            int row = matrix.length - 1;
            int y = 0;
            if(matrix.length == 0||matrix[0].length == 0)
                return false; 
            if(matrix[0][0] > target || matrix[row][matrix[0].length-1] < target)
                return false;
            while(row >= 0 && y < matrix[0].length ){
                
                if(matrix[row][y] == target)
                    return true;
                else if(matrix[row][y] > target)
                    row--;
                else
                    y++;
            }
            return false;
        }
    }