手帐 Blog

主题

复盘 · LC 240 搜索二维矩阵 II ​

题目 ​

题意 ​

在 m × n 矩阵中判断是否存在 target。矩阵性质：

  • 每行从左到右升序；
  • 每列从上到下升序。

注意：这和 74. 搜索二维矩阵 不同——74 可以看成「整表一行拼起来有序」；240 只能保证行、列各自有序，不能直接对整表一次二分。

边界：空矩阵；target 小于左上/大于右下；落在中间某行中间列。

涉及算法 ​

标签一句话
逐行二分每行有序 → 对每行 lower_bound，总 O(m log n)
右上角缩小从右上（或左下）出发，一次比较砍掉一行或一列，O(m+n)

教程对照：14 · 二分查找标准模板；二维有序结构也可对照 15 · 二分变体 的「缩小搜索空间」直觉。

评价我的解法 ​

两版：先暴力差点 TLE，再逐行二分 AC——进步清晰，但仍未用到本题最优形态。

第一版：双层遍历（TLE） ​

摘自 index.js：

javascript
var searchMatrix = function (matrix, target) {
  const xLen = matrix[0].length;
  const yLen = matrix.length;
  let isFind = false;
  for (let y = 0; y < yLen; y++) {
    for (let x = 0; x < xLen; x++) {
      const item = matrix[y][x];
      if (item === target) {
        isFind = true;
        break;
      }
      if (item >= target) {
        continue;
      }
    }
    if (isFind) {
      break;
    }
  }
  return isFind;
};

问题：

  1. 仍是 O(mn)：item >= target 时 continue 几乎没剪枝；行内已有序，item > target 应 break 本行，不是 continue。
  2. 没用列有序：240 的杀手锏是行列双有序，暴力等于浪费题设。
  3. 126/130 TLE——大样例暴露复杂度。

第二版：逐行二分（AC，主解） ​

我的代码（摘自 index2.js）：

javascript
function leftBound(nums = [], target) {
  let left = 0;
  let right = nums.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (nums[mid] >= target) {
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
  if (left >= nums.length || nums[left] !== target) {
    return -1;
  }
  return left;
}

var searchMatrix = function (matrix, target) {
  const yLen = matrix.length;
  let isFind = false;
  for (let y = 0; y < yLen; y++) {
    const res = leftBound(matrix[y], target);
    if (res !== -1) {
      isFind = true;
      break;
    }
  }
  return isFind;
};

对在哪：

  • leftBound 模板正确（找第一个 >= target，再验相等）——说明 14 有落地。
  • 正确性没问题，能 AC。

糙在哪：

  1. 复杂度档位：O(m log n)，提交约 2741ms、约 5%——偏慢但仍可过。
  2. 没用列有序：最优是从右上角「大了往左、小了往下」，O(m+n)，常数也好。
  3. 写法：isFind 可直接 return true/false；leftBound 默认参数在刷题里可省略。

小结：从 TLE 到二分是对的；下一步把「二维有序 → 角点收缩」默进肌肉。

最佳题解 ​

从右上角出发（经典）：

javascript
/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function (matrix, target) {
  if (!matrix.length) return false;
  let row = 0;
  let col = matrix[0].length - 1;
  while (row < matrix.length && col >= 0) {
    const val = matrix[row][col];
    if (val === target) return true;
    if (val > target) col--;
    else row++;
  }
  return false;
};
  • 时间 O(m+n)，空间 O(1)。
  • 为何更优：每次比较要么删一整列，要么删一整行；同时吃到行升序和列升序，比「只吃行」的逐行二分更贴题设。

关联题目 ​

题为何相关
74. 搜索二维矩阵更强有序，可一次二分整表
378. 有序矩阵中第 K 小的元素同结构，答案二分 / 堆
34. 在排序数组中查找元素的第一个和最后一个位置巩固 leftBound

一句话带走 ​

240：别整表暴力；右上角起步，大了向左、小了向下；逐行二分只是保底。