240.搜索二维矩阵II

链接：240.搜索二维矩阵II
难度：Medium
标签：数组、二分查找、分治、矩阵
简介：编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。

题解 1 - typescript

• 编辑时间：2021-10-25
• 执行用时：96ms
• 内存消耗：43.1MB
• 编程语言：typescript
• 解法介绍：拆分查找。

function searchMatrix(matrix: number[][], target: number): boolean {
  return matrix.flat().includes(target);
}

题解 2 - typescript

• 编辑时间：2021-07-24
• 执行用时：72ms
• 内存消耗：40.8MB
• 编程语言：typescript
• 解法介绍：从右上角开始寻找。

function searchMatrix(matrix: number[][], target: number): boolean {
  let i = 0;
  let j = matrix[0].length - 1;
  while (i < matrix.length && j >= 0) {
    if (matrix[i][j] > target) j--;
    else if (matrix[i][j] < target) i++;
    else return true;
  }
  return false;
}

题解 3 - typescript

• 编辑时间：2021-10-25
• 执行用时：72ms
• 内存消耗：41MB
• 编程语言：typescript
• 解法介绍：从右上角开始找，target 就左移，target 大就下移。

function searchMatrix(matrix: number[][], target: number): boolean {
  const m = matrix.length;
  const n = matrix[0].length;
  let row = 0;
  let col = n - 1;
  while (row < m && col >= 0) {
    const num = matrix[row][col];
    if (num === target) return true;
    if (num > target) col--;
    else row++;
  }
  return false;
}