剑指offer 二维数组中的查找

剑指offer60天计划

Posted by liuwenzi on July 21, 2020
阅读数:

二维数组中的查找


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

题解

  • 遍历二维数组

    • 空间复杂度O(1)
    • 时间复杂度O(n)

    uxAfDJ

  • 利用每一行从左到右递增,每一列从上到下递增的顺序排序的特征,将二维数组画成矩形,从二维数组的右上角或者左下角开始搜寻。左下角为例,当左下角元素小于目标元素时,将左边一列剔除,当左下角元素大于目标元素时,则将最后一行剔除。以此类推,直到找到元素

    • 时间复杂度O(n)

    • 空间复杂度O(1)

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      
      class Solution {
          public boolean findNumberIn2DArray(int[][] matrix, int target) {
            	if(matrix == null){
                return false;
              }
              int i = matrix.length - 1, j = 0;
          
              while(i >= 0 && j <= matrix[0].length -1)
              {
                  if(matrix[i][j] > target){
                      i--;
                  }else if(matrix[i][j] < target){
                      j++;
                  }else{
                      return true;
                  }
                  
              return false;
          
          }
      }
      

      

      Dl15uv

总结