【杂题】剑指 Offer 04. 二维数组中的查找

共以下 6 个回答

• YULONG 永久会员 2024年10月26日 上午2:12

  // 1.暴力法
  // 遍历二维矩阵，复杂度 O(m*n)

  // 2.排除法
  // 初始(x, y)为右上角(0, m-1)
  // 如果target > matrix[x][y], 则第0行元素都比target小，可以舍弃, 坐标更新为(x+1, y)， 继续查找
  // 如果target < matrix[x][y], 则第j列元素都比target大，可以舍弃，坐标更新为(x, y-1)， 继续查找
  // target matrix[x][y] 返回TRUE，x,y越界也没有找到返回false
  // 最坏情况为数据在左下角,恰好遍历完一行和一列, 时间复杂度O(m+n), 空间复杂度O(1)

  // 3.二分查找, 每一行做一次二分，复杂度O(m*logn)

  class Solution {
  
      // 排除法O(m+n)
      public boolean findTargetIn2DPlantsPCF(int[][] matrix, int target) {
          if (matrix == null || matrix.length == 0){
              return false;
          }
  
          int m = matrix.length, n = matrix[0].length;
          int i = 0, j = n-1;
  
          while (i < m && j >= 0){
              if (matrix[i][j] == target){
                  return true;
              } else if (matrix[i][j] > target){
                  j--;
              } else{
                  i++;
              }
          }
          return false;
      }
  
      // 二分写法 O(m*logn)
      public boolean findTargetIn2DPlants(int[][] matrix, int target) {
          if (matrix == null || matrix.length == 0){
              return false;
          }
  
          int m = matrix.length, n = matrix[0].length;
  
          for (int i = 0; i < m; i++){
              int left = 0, right = n;
              while (left < right){
                  int mid = left + (right - left) / 2;
                  if (matrix[i][mid] == target){
                      return true;
                  } else if (matrix[i][mid] > target){
                      right = mid;
                  } else{
                      left = mid + 1;
                  }
              }
          }
  
  
          return false;
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• 王位詮釋 普通 2024年4月15日 下午2:25

  暴力法：
  class Solution {
      public boolean findTargetIn2DPlants(int[][] plants, int target) {
          //暴力法
          if(plants==null||plants.length==0){
              return false;
          }
          int m = plants.length;
          int n = plants[0].length;
          for(int i=0;i<m;i++){
              for(int j=0;j<n;j++){
                  if(plants[i][j]==target){
                      return true;
                  }
              }
          }
          return false;
      }
  }
  时间复杂度：O(n2)
  空间复杂度：O(1)
  

  最优解：
  class Solution {
      public boolean findTargetIn2DPlants(int[][] plants, int target) {
          if(plants==null||plants.length<=0){
              return false;
          }
          int i = plants.length-1;
          int j = 0;
          while(i>=0&&j<plants[0].length){
              if(plants[i][j]==target){
                  return true;
              }
              if(plants[i][j]<target){
                  j++;
              }else{
                  i--;
              }
          }
          return false;
      }
  }
  时间复杂度：O(m+n)
  空间复杂度：O(1)
  

  0 赞同 0 条回复

  登录以回复
• 白雪公主倒拔垂杨柳 永久会员 2024年4月10日 下午3:40

  class Solution {
      public boolean findTargetIn2DPlants(int[][] plants, int target) {
          if(plants ==null || plants.length<=0 || plants[0].length<=0) return false;
          int rows = plants.length;
          int cols = plants[0].length;
  
          // //左下角
          // int row = rows-1;
          // int col = 0;
          // while(row>=0 && col<cols){
          //     if(plants[row][col]<target){
          //         col++;
          //     }else if(plants[row][col]>target){
          //         row--;
          //     }else{
          //         return true;
          //     }
          // }
  
          //试试右上角
          int row = 0;
          int col = cols-1;
          while(row<rows && col>=0){
              if(plants[row][col]<target){
                  row++;
              }else if(plants[row][col]>target){
                  col--;
              }else{
                  return true;
              }
          }
  
          return false;
      }
  }
  

  时间复杂度：O(n+m)
  额外空间复杂度：O(1)

  0 赞同 0 条回复

  登录以回复
• 云无深雁影 普通 2024年4月8日 下午11:53

  class Solution {
  public boolean findTargetIn2DPlants(int[][] plants, int target) {
  int i = 0, j = 0;
  while(i >= 0 && j >= 0 && i < plants.length && j < plants[0].length){
  if(target plants[i][j])
  return true;
  else if(target > plants[i][j]){
  if(j < plants[0].length-1 && plants[i][j+1] <= target)
  j++;
  else
  i++;
  }else{
  j–;
  }
  }
  return false;
  }
  }
  //时间Onm
  //空间O1

  0 赞同 0 条回复

  登录以回复
• Jimmy 普通 2024年4月8日 下午10:53

  二分+暴力

  class Solution {
  public:
      bool findTargetIn2DPlants(vector<vector<int>>& plants, int target) {
          for(int i=0;i<plants.size();i++)
          {
              if(binarySearch(plants[i],target))
              {
                  return true;
              }
          }
          return false;
      }
  
      bool binarySearch(vector<int>& subplants, int target)
      {
          int left = 0;
          int right = subplants.size()-1;
          while(left <= right)
          {
              int mid = left + (right-left)/2;
              if(subplants[mid] > target)
              {
                  right = mid - 1;
              }
              else if(subplants[mid] < target)
              {
                  left = mid + 1;
              }
              else
              {
                  return true;
              }
          }
          return false;
      }
  };
  

  0 赞同 0 条回复

  登录以回复
• 紫芝 普通 2024年4月5日 下午8:58

  时间：O(m+n)
  空间：O(1)

  “`c++
  class Solution {
  public:
  bool findTargetIn2DPlants(vector>& plants, int target) {
  if (plants.size() == 0) return false;
  int m = plants.size(), n = plants[0].size();
  int i = 0, j = n-1;
  while (i < m && j >= 0) {
  if (plants[i][j] > target) j–;
  else if (plants[i][j] < target) i++; else return true; } return false; } }; ```

  0 赞同 0 条回复

  登录以回复