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

题目描述

在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

?示例:

?现有矩阵 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。

?限制：

?0 <= n <= 1000

?0 <= m <= 1000

题解

?在矩阵的左下角上的数，所有正上方的数比他小，所有正右方的数比他大。所以从矩阵左下角的第一个数开始循环，记当前数为current，目标数为target。

1. 如果current比target小，current向右移；
2. 如果current比target大，current向左移；
3. 如果current等于target，则返回true；
4. 如果直到矩阵右上角还没找到target，就返回false。

?时间复杂度O(m+n)

?空间复杂度O(1)

代码

class Solution {

  public boolean findNumberIn2DArray(int[][] matrix, int target) {

    if(matrix==null||matrix.length==0||(matrix.length==1 && matrix[0].length==0)){
      //数组可能不存在：matrix=null
      //数组可能为空：
      // 1.{}:matrix.length==0
      // 2.{{}}:matrix.length==1 && matrix[0].length==0

      return false;

    }

    int x=matrix.length-1;

    int y=0;



    while(x>=0 && y<matrix[0].length){

      //这里y要小于matrix[0].length

      //matrix[0].length是二维数组的列数

      //matrix.length是二维数组的行数

      if(matrix[x][y]>target){

        x--;

      }

      else if (matrix[x][y]<target){

        y++;

      }

      else{

        return true;

      }

    }

    return false;

  }

}

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

原文：https://www.cnblogs.com/simpleName/p/14613271.html