240. 搜索二维矩阵 II

题目描述

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：

• 每行的元素从左到右升序排列。
• 每列的元素从上到下升序排列。

示例 1：

输入：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

示例 2：

输入：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 = 20

输出：false

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= n, m <= 300
• -10^9 <= matrix[i][j] <= 10^9
• -10^9 <= target <= 10^9

出处：LeetCode

解法一：直接遍历

思路

我们直接遍历整个矩阵 matrix，判断 target 是否出现即可。

实现

function searchMatrix(matrix: number[][], target: number): boolean {
  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 \times n)$
• 空间复杂度：$O(1)$

解法二：二分查找

思路

我们可以从矩阵的右上角开始查找，如果当前元素比目标值大，则向左移动一列，如果当前元素比目标值小，则向下移动一行。

实现

function searchMatrix(matrix: number[][], target: number): boolean {
  if (!matrix.length || !matrix[0].length) {
    return false;
  }

  const m = matrix.length;
  const n = matrix[0].length;

  let row = 0;
  let col = n - 1;

  while (row < m && col >= 0) {
    if (matrix[row][col] === target) {
      return true;
    } else if (matrix[row][col] > target) {
      col--;
    } else {
      row++;
    }
  }

  return false;
}

复杂度分析

• 时间复杂度：$O(m + n)$
• 空间复杂度：$O(1)$

解法三：Z 字形遍历

思路

我们可以从矩阵的左下角开始查找，如果当前元素比目标值大，则向上移动一行，如果当前元素比目标值小，则向右移动一列。

实现

function searchMatrix(matrix: number[][], target: number): boolean {
  if (!matrix.length || !matrix[0].length) {
    return false;
  }

  const m = matrix.length;
  const n = matrix[0].length;

  let row = m - 1;
  let col = 0;

  while (row >= 0 && col < n) {
    if (matrix[row][col] === target) {
      return true;
    } else if (matrix[row][col] > target) {
      row--;
    } else {
      col++;
    }
  }

  return false;
}