知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 77 - 搜索二维矩阵II ## 题目(LeetCode 240) 在每行每列都递增的 m×n 矩阵中搜索目标值。 ## 解法:从右上角开始 ```java class Solution { public boolean searchMatrix(int[][] matrix, int target) { int i = 0, j = matrix[0].length - 1; //每次必排序一列或者一行,从右上角开始 while (i < matrix.length && j >= 0) { //找到了就返回 if (matrix[i][j] == target){ return true; }else if (matrix[i][j] > target){ //如果目标值比当前值小,因为此时已经是该列最小值了,排序该列 j--; }else{ //目标值比当前直大,当前值是该行的最大值,往下一行找了 i++; } } return false; } } ``` > 💬 **Q:这种解法的思想是什么?给出示例** > > 这叫 **Z 字形搜索**,从右上角出发,利用矩阵的有序性每次排除一整行或一整列。 > > ``` > 矩阵特性:每行从左到右递增,每列从上到下递增 > > 右上角 matrix[i][j] 的特殊性: > 它是当前行的最大值(右边没有了) > 它是当前列的最小值(上面没有了) > > 所以: > matrix[i][j] == target → 找到了 > matrix[i][j] > target → target 比整列最小值还小,这列排除,j-- > matrix[i][j] < target → target 比整行最大值还大,这行排除,i++ > ``` > > 用 `target = 5` 演示: > > ``` > 1 4 7 [11] ← 从右上角 (0,3)=11 开始 > 2 5 8 12 > 3 6 9 16 > 10 13 14 17 > > (0,3)=11 > 5 → 11 是第3列最小值,5 比它还小,整列排除,j=2 > 1 4 [7] × > 2 5 8 × > 3 6 9 × > 10 13 14 × > > (0,2)=7 > 5 → 整列排除,j=1 > 1 [4] × × > 2 5 × × > 3 6 × × > 10 13 × × > > (0,1)=4 < 5 → 4 是第0行最大值,5 比它还大,整行排除,i=1 > × × × × > 2 [5] × × > 3 6 × × > 10 13 × × > > (1,1)=5 == 5 → 找到!返回 true > > 走的路径:11 → 7 → 4 → 5,像 Z 字形斜着走 > ``` > > 每步必然排除一行或一列,最多走 m+n 步,时间复杂度 O(m+n),远优于暴力的 O(m×n)。 ## 复杂度 - 时间 O(m+n),空间 O(1) ## 一句话总结 从右上角出发,大了往左走,小了往下走。 ## 说明 从右上角(或左下角)出发是这道题的最优解,利用了矩阵行列有序的性质,每步可以排除一行或一列,达到 O(m+n)。 二分查找可以对每行单独做,时间 O(m log n),不如当前解法。当前解法已是最优。
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入