240. 搜索二维矩阵 II

题目

思路一 暴力求解

复杂度

时间复杂度 O(m * n)

空间复杂度 O(1)

编码

function searchMatrix(matrix, target) {
  for (let i = 0; i < matrix.length; i++) {
    for (let j = 0; j < matrix[i].length; j++) {
      if (matrix[i][j] === target) return true;
    }
  }
  return false;
}

思路二 二分查找

简单利用每一行有序的特性进行二分查找。

复杂度

时间复杂度 O(m * logn)

空间复杂度 O(1)

编码

function binarySearch(arr, target) {
  let l = 0, r = arr.length - 1;
  while (l <= r) {
    let mid = (l + r) >> 1;
    if (arr[mid] > target) r = mid - 1;
    else if (arr[mid] < target) l = mid + 1;
    else return true;
  }
  return false;
}
function searchMatrix(matrix, target) {
  for (let i = 0; i < matrix.length; i++) {
    if (binarySearch(matrix[i], target)) return true;
  }
  return false;
}

思路三 Z字形查找

也带有一点二分查找的思想。对于矩阵来说整体平铺并不是有序的，但从矩阵的右上角开始，往左是单调递减的，往下是单调递增的。那么，我们以右上角为中点，如果中点大于目标，则要往左移动，反之往下移动，整过过程是从矩阵右上角往左下角的z字形查找，最坏情况则是从矩阵右上角到左下角的距离m+n。
另外，把矩阵逆时针旋转个45°就成了二叉搜索树了，不过这里我们的元素之间不是相连节点，所以还是当作是Z字形查找。

复杂度

时间复杂度 O(m + n)

空间复杂度 O(1)

编码

function searchMatrix(matrix, target) {
  if (!matrix.length) return false;
  let x = matrix[0].length - 1;
  let y = 0;
  while (true) {
    let mid = matrix[y][x];
    if (mid === target) return true;
    else if (mid > target && x > 0) x -= 1;
    else if (mid < target && y < (matrix.length - 1)) y += 1;
    else return false;
  }
}