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

共以下 1 个回答

• 塔底的仰望 永久会员 2023年9月17日 下午9:23

  对角线上的元素是那一行向下以及向右最小的元素
  假设n < m
  时间复杂度O(nlogm)空间复杂度O(1)

  class Solution {
      public boolean findNumberIn2DArray(int[][] matrix, int target) {
          if (matrix.length == 0 || matrix[0].length == 0) {
              return false;
          }
          int min = Math.min(matrix.length, matrix[0].length);
          for (int i = 0; i < min; i++) {
              if (matrix[i][i] > target) {
                  return false;
              }
              if (search(matrix, target, i)) {
                  return true;
              }
          }
          return false;
      }
  
      public boolean search(int[][] matrix, int target, int pos) {
          int n = matrix.length;
          int m = matrix[0].length;
          //两次二分搜索
          int l = pos;
          int r = n - 1;
          while (l <= r) {
              int mid = (r - l) /2 + l;
              if (matrix[mid][pos] == target) {
                  return true;
              } else if (matrix[mid][pos] > target) {
                  r = mid - 1;
              } else {
                  l = l + 1;
              }
          }
          l = pos;
          r = m - 1;
          while (l <= r) {
              int mid = (r - l) /2 + l;
              if (matrix[pos][mid] == target) {
                  return true;
              } else if (matrix[pos][mid] > target) {
                  r = mid - 1;
              } else {
                  l = l + 1;
              }
          }
  
          return false;
  
      }
  }
  

  0 赞同 0 条回复

  登录以回复