74.搜索二维矩阵

链接：74.搜索二维矩阵
难度：Medium
标签：数组、二分查找、矩阵
简介：编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。

题解 1 - typescript

• 编辑时间：2021-03-30
• 执行用时：84ms
• 内存消耗：39.4MB
• 编程语言：typescript
• 解法介绍：二分查找。

function searchMatrix(matrix: number[][], target: number): boolean {
  const colLen = matrix[0].length;
  const rowLen = matrix.length;
  const findRow = (start: number, end: number): number[] | undefined => {
    if (start > end) return undefined;
    const mid = ~~((start + end) / 2);
    const row = matrix[mid];
    if (row[0] > target) return findRow(start, mid - 1);
    else if (row[colLen - 1] < target) return findRow(mid + 1, end);
    else return row;
  };
  const targetRow: number[] | undefined = findRow(0, rowLen - 1);
  if (!targetRow) return false;
  const findTarget = (start: number, end: number): boolean => {
    if (start > end) return false;
    const mid = ~~((start + end) / 2);
    if (targetRow[mid] < target) return findTarget(mid + 1, end);
    else if (targetRow[mid] > target) return findTarget(start, mid - 1);
    else return true;
  };
  return findTarget(0, colLen - 1);
}

题解 2 - typescript

• 编辑时间：2021-03-30
• 执行用时：88ms
• 内存消耗：39.2MB
• 编程语言：typescript
• 解法介绍：根据特性把二维数据当作一维进行运算。

function searchMatrix(matrix: number[][], target: number): boolean {
  const colLen = matrix[0].length;
  const rowLen = matrix.length;
  const find = (start: number, end: number): boolean => {
    if (start > end) return false;
    const mid = ~~((start + end) / 2);
    const row = ~~(mid / colLen);
    const col = mid % colLen;
    if (matrix[row][col] < target) return find(mid + 1, end);
    else if (matrix[row][col] > target) return find(start, mid - 1);
    else return true;
  };
  return find(0, colLen * rowLen - 1);
}

题解 3 - typescript

• 编辑时间：2021-03-30
• 执行用时：84ms
• 内存消耗：39.3MB
• 编程语言：typescript
• 解法介绍：二分查找。

function searchMatrix(matrix: number[][], target: number): boolean {
  const colLen = matrix[0].length;
  const rowLen = matrix.length;
  let targetRow!: number[];
  for (let i = 0; i < rowLen; i++) {
    const row = matrix[i];
    if (i === rowLen - 1) {
      targetRow = row;
    } else if (row[0] <= target && matrix[i + 1][0] > target) {
      targetRow = row;
      break;
    }
  }
  if (!targetRow) return false;
  const find = (start: number, end: number): boolean => {
    if (start > end) return false;
    const mid = ~~((start + end) / 2);
    if (targetRow[mid] < target) return find(mid + 1, end);
    else if (targetRow[mid] > target) return find(start, mid - 1);
    else return true;
  };
  return find(0, colLen - 1);
}