题目

image.png

思路

  • 左下角的元素是这一行中最小的元素，同时又是这一列中最大的元素。比较左下角元素和目标：
    • 若左下角元素等于目标，则找到
    • 若左下角元素大于目标，则目标不可能存在于当前矩阵的最后一行，问题规模可以减小为在去掉最后一行的子矩阵中寻找目标
    • 若左下角元素小于目标，则目标不可能存在于当前矩阵的第一列，问题规模可以减小为在去掉第一列的子矩阵中寻找目标
  • 若最后矩阵减小为空，则说明不存在

    代码

    1.   public boolean searchMatrix(int[][] matrix, int target) {
    2.       int m = matrix.length, n = matrix[0].length;
    3.       if (m == 0 || n == 0) return false;
    4.       int i = 0, j = n - 1;
    5.       while (i < m && j >= 0) {
    6.           if (matrix[i][j] == target) {
    7.               return true;
    8.           } else if (matrix[i][j] < target) {
    9.               i++;
    10.           } else {
    11.               j--;
    12.           }
    13.       }
    14.       return false; 
    15.   }
    搜索二维矩阵II