.jpg)
469 字
2 分钟
搜索二维矩阵 II
.png)
题目描述
编写一个高效的算法来搜索 _m_ x _n_ 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
- 每行的元素从左到右升序排列。
- 每列的元素从上到下升序排列。
解题思路
- 对角线起点选择：
- 从右上角（或左下角）开始搜索
- 利用行列有序特性缩小范围
- 决策路径优化：
- 当前值 < target → 下移（排除当前行）
- 当前值 > target → 左移（排除当前列）
- 当前值 = target → 返回成功
- 边界终止条件：
- 行索引超出矩阵底部
- 列索引超出矩阵左边界
- 方向特性利用：
- 右上角：左小下大
- 左下角：右小上大
关键洞察
- 矩阵特性利用：
- 行列方向独立有序
- 对角线形成阶梯状递增
- 搜索路径最优性：
- 每次移动排除一行/列
- 避免无效区域扫描
- 起点选择优势：
- 右上角/左下角是决策枢纽点
- 提供最大比较信息
- 无回溯机制：
- 移动路径是单向收敛的
- 不会遗漏可能区域
复杂度分析
| 指标 | 说明 |
|---|---|
| 时间复杂度 | O(m+n)：最坏情况遍历一行一列长度之和 |
| 空间复杂度 | O(1)：仅使用常数额外变量 |
代码实现
/** * @param {number[][]} matrix * @param {number} target * @return {boolean} */var searchMatrix = function (matrix, target) { const m = matrix.length; const n = matrix[0].length;
let x = 0, y = n - 1;
while (x < m && y >= 0) { if (matrix[x][y] === target) return true; if (matrix[x][y] > target) { y--; } else { x++; } }
return false};实际应用场景
- 电商系统：商品价格-库存矩阵中查找特定组合`
- 地理信息系统：海拔矩阵中搜索特定高度区域`
- 图像处理：在有序像素矩阵中定位特定颜色值