02.5.1.4 二维矩阵与非数组二分
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.5 二分与排序 / 02.5.1 二分查找
02.5.1.4-001 二维有序矩阵有哪两种形态?
一句话结论
形态一:每行有序且下一行首元素 ≥ 上一行尾元素,可视为一维有序数组;形态二:行列各自有序但行间不保证衔接,需按行列排除;先判断属于哪种。
概念解释
- 全矩阵有序。
- 行列局部有序。
- 排除策略不同。
原理流程
- 比较行首尾衔接。
- 全有序映射一维。
- 局部有序按行列收缩。
代码 / 图示
形态一:每行尾 ≤ 下行首
形态二:行升序、列升序,行间不衔接
常见误区
- 误区:两种形态用同一模板;正解:先确认衔接关系。
- 误区:行列有序即全局有序;正解:形态二不保证。
追问
- Q:LC 74 是哪种? A:形态一。
- Q:LC 240 是哪种? A:形态二。
02.5.1.4-002 搜索二维矩阵 I(LC 74)怎么做?
一句话结论
全矩阵可展平为长度 m*n 的一维有序数组;下标 mid 映射 (mid/n, mid%n) 做普通二分;O(log(mn)) 时间 O(1) 空间。
概念解释
- 一维映射。
- 行列换算。
- 普通二分。
原理流程
- 展平下标区间
[0, mn)。 - mid 换算行列。
- 比较收缩。
代码 / 示例
public boolean searchMatrix(int[][] m, int target) {
int rows = m.length, cols = m[0].length;
int l = 0, r = rows * cols - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
int val = m[mid / cols][mid % cols];
if (val == target) return true;
if (val < target) l = mid + 1;
else r = mid - 1;
}
return false;
}
常见误区
- 误区:行与列都取 n;正解:列数固定,行 = mid/cols。
- 误区:空矩阵未判;正解:先判行列长度。
追问
- Q:映射下标 0 起? A:按数组 0 起口径。
- Q:矩阵元素重复? A:等值二分仍可判存在。
02.5.1.4-003 搜索二维矩阵 II(LC 240)怎么做?
一句话结论
行列各自有序但不衔接;从右上角起步:当前值大于 target 左移一列,小于 target 下移一行;O(m+n) 时间 O(1) 空间;不能直接一维二分。
概念解释
- 右上角:左小下大。
- 行列排除。
- 折线搜索。
原理流程
- 从右上开始。
- 大则列左移。
- 小则行下移。
代码 / 示例
public boolean searchMatrix(int[][] m, int target) {
int row = 0, col = m[0].length - 1;
while (row < m.length && col >= 0) {
if (m[row][col] == target) return true;
if (m[row][col] > target) col--;
else row++;
}
return false;
}
常见误区
- 误区:展平一维二分;正解:行间不衔接,不可展平。
- 误区:从左上角起步;正解:左上角两个方向都变大,无法排除。
追问
- Q:复杂度为什么 O(m+n)? A:行列各最多移动一次。
- Q:能否二分加速? A:可对每行二分 O(m log n),折线法更直接。
02.5.1.4-004 矩阵下标怎么映射一维?
一句话结论
idx = row * cols + col;逆映射 row = idx / cols,col = idx % cols;前提是行优先展平且矩阵等宽;换算时注意列数常量。
概念解释
- 行优先编号。
- 整除与取模。
- 等宽前提。
原理流程
- 展平按行排列。
- 乘列数加列号。
- 逆映射还原。
代码 / 图示
idx → (idx / cols, idx % cols)
常见误区
- 误区:误用行数换算;正解:除列数。
- 误区:列宽不一致;正解:等宽矩阵才适用。
追问
- Q:列优先? A:
idx = col*rows+row,口径对应。 - Q:下标溢出? A:
rows*cols注意 int 范围。
02.5.1.4-005 右上角搜索法为什么能排除行列?
一句话结论
右上角元素是该行最大、该列最小;比 target 大则该行右侧无需再看(左移),比 target 小则该列上方无需再看(下移);每次排除一行或一列。
概念解释
- 位置性质。
- 单向排除。
- 折线收敛。
原理流程
- 右上角行最大列最小。
- 大:排除当前行右侧。
- 小:排除当前列上方。
代码 / 图示
← 列
行 ↓ 右上
常见误区
- 误区:排除整行还是整列混淆;正解:大移列,小移行。
- 误区:起点选错导致双向都无法排除;正解:选角部单调方向。
追问
- Q:左下角对称版本? A:行最小列最大,方向镜像。
- Q:什么矩阵不能用? A:行或列无序。
02.5.1.4-006 矩阵二分复杂度怎么算?
一句话结论
全有序一维映射 O(log(mn));行列有序折线法 O(m+n);每行二分 O(m log n);空间 O(1);按矩阵形态选策略。
概念解释
- 形态决定策略。
- 行列规模。
- 辅助常数。
原理流程
- 判断矩阵形态。
- 统计行列规模。
- 标注时间空间。
代码 / 图示
全有序:O(log mn)
行列有序:O(m+n) / O(m log n)
常见误区
- 误区:行列有序也报 O(log mn);正解:不衔接不可折半。
- 误区:折线法 O(mn);正解:行列各移动一次。
追问
- Q:方形矩阵? A:O(n) 折线。
- Q:稀疏矩阵? A:按实际存储另议。
02.5.1.4-007 有序矩阵第 K 小(LC 378)怎么做?
一句话结论
行列各自升序;二分答案数值 x,统计 ≤ x 的元素个数;个数 ≥ K 则尝试更小,否则更大;check 用每行二分或折线计数 O(m log n);O(n log n · log R)。
概念解释
- 二分答案。
- 计数判定。
- 行列有序辅助。
原理流程
- 值域在矩阵最小最大间。
- check 统计 ≤ mid 个数。
- 收敛第 K 小。
代码 / 示例
public int kthSmallest(int[][] m, int k) {
int l = m[0][0], r = m[m.length - 1][m[0].length - 1];
while (l < r) {
int mid = l + (r - l) / 2;
if (countLe(m, mid) >= k) r = mid;
else l = mid + 1;
}
return l;
}
// 每行二分统计 ≤ mid 个数,或折线从右上计数
常见误区
- 误区:堆取前 K 个 O(k log n);正解:K 大时二分答案更稳。
- 误区:统计未利用行列有序;正解:每行二分或折线 O(m+n) 计数。
追问
- Q:堆做法? A:小顶堆首列起步,弹出 K 次。
- Q:mid 不在矩阵中? A:收敛边界即矩阵内第 K 小。
02.5.1.4-008 二维峰值元素怎么找?
一句话结论
二维网格中峰值大于四邻居;可逐行二分找行内峰值列,再比较上下行该列值调整行方向;或按行/列折半;局部性质可二分排除一侧。
概念解释
- 四邻居。
- 行列调整。
- 局部最大。
原理流程
- 取行内最大列。
- 与上下比较。
- 高处行继续。
代码 / 图示
当前格 ≥ 上下 → 峰值
下方更大 → 下移行
常见误区
- 误区:全局有序才找峰值;正解:局部比较可排除侧。
- 误区:只看左右邻居;正解:二维含上下。
追问
- Q:LC 162 一维峰值? A:见 02.5.1.1-013 思路。
- Q:边界格邻居? A:缺邻居按比较处理。
02.5.1.4-009 二维矩阵遍历与二分怎么衔接?
一句话结论
先判断矩阵有序形态,全有序套一维二分;局部有序套行列折线;需要统计计数时结合每行二分;二维前缀和等遍历问题不属于二分。
概念解释
- 形态判断。
- 策略选择。
- 边界区分。
原理流程
- 看行首尾衔接。
- 选一维/折线。
- 计数再二分答案。
代码 / 图示
衔接 → 一维二分
不衔接 → 折线
常见误区
- 误区:所有矩阵题都二分;正解:无序遍历用 DFS/BFS。
- 误区:折线法用于全有序;正解:全有序二分更快。
追问
- Q:岛屿遍历? A:DFS/BFS,见 02.4.2.1。
- Q:矩阵求和? A:前缀和,见 02.2.1。
02.5.1.4-010 非数组的二分能用在什么上?
一句话结论
只要候选空间在某个有序维度上单调,即可二分:整数答案、单调函数求根、离散有序集合、区间定位、BST 查找;本质都是折半排除一半候选。
概念解释
- 有序候选空间。
- 判定比较。
- 折半通用。
原理流程
- 找有序维度。
- 中点判定。
- 排除一侧。
代码 / 图示
函数 f(x) 单调 → 求零点
BST 按值 → 走子树
常见误区
- 误区:二分只能用于数组;正解:单调候选空间均可。
- 误区:树结构上二分按数组下标;正解:按树分支比较。
追问
- Q:BST 查找复杂度? A:O(h),见 02.4.1.2。
- Q:函数求根? A:二分零点,需单调连续。
02.5.1.4-011 单调函数怎么用二分求根?
一句话结论
函数单调连续,零点两侧符号相反;中点比较符号(或与目标值比较),缩小区间到精度;整数根用整数二分,浮点根按精度迭代。
概念解释
- 单调连续。
- 符号分界。
- 精度收敛。
原理流程
- 找符号相反区间。
- 中点算值比较。
- 收缩到精度。
代码 / 图示
f(l)·f(r) < 0 → 区间含根
常见误区
- 误区:非单调函数二分求根;正解:可能漏掉多个根。
- 误区:浮点死循环;正解:固定轮次或 eps。
追问
- Q:求平方根? A:f(x)=x²-n,见 02.5.1.1-011。
- Q:离散函数? A:按离散点二分。
02.5.1.4-012 离散有序集合怎么二分?
一句话结论
元素存数组/链表式有序集合中,下标对应排名;数组支持随机访问可二分;有序链表不支持 O(1) 访问,不能高效二分;映射到下标后套模板。
概念解释
- 随机访问。
- 排名下标。
- 结构限制。
原理流程
- 确认可随机访问。
- 下标二分。
- 定位元素。
代码 / 图示
有序数组:可二分
有序链表:线性访问
常见误区
- 误区:有序链表二分;正解:访问中点需 O(n)。
- 误区:集合有重复未排序;正解:先排序。
追问
- Q:TreeSet 查找? A:红黑树 O(log n),非数组二分。
- Q:排名查询? A:平衡树/下标数组。
02.5.1.4-013 区间定位类二分是什么?
一句话结论
候选是区间(如插入位置、区间覆盖归属),二分找到区间边界;与 lower_bound 同源,返回左/右边界下标;常配合区间合并问题。
概念解释
- 边界定位。
- 区间归属。
- 上下界模板。
原理流程
- 区间有序排列。
- 二分定位边界。
- 返回归属区间。
代码 / 图示
[1,3) [3,5) [5,8) → 二分找所属段
常见误区
- 误区:区间端点重叠归属写错;正解:开闭口径统一。
- 误区:线性扫描区间;正解:有序可二分。
追问
- Q:合并区间? A:排序贪心,见 02.2.1。
- Q:日程安排? A:有序区间二分定位。
02.5.1.4-014 BST 上的二分是什么思路?
一句话结论
BST 按值比较:小走左子树、大走右子树;每次排除一棵子树,O(h);与数组二分同属折半思想,但比较对象是节点值而非下标。
概念解释
- 值比较。
- 子树排除。
- 树高口径。
原理流程
- 当前节点比较。
- 小走左,大走右。
- 命中或到空。
代码 / 图示
target < node → 左
target > node → 右
常见误区
- 误区:BST 二分 O(log n) 恒成立;正解:退化链 O(h)=O(n)。
- 误区:按数组下标走;正解:按指针分支。
追问
- Q:平衡 BST 高度? A:O(log n)。
- Q:详细 BST 操作? A:见 02.4.1.2。
02.5.1.4-015 矩阵与非数组二分有哪些边界用例?
一句话结论
单行、单列、空矩阵、单元素、target 越界、全相同值、矩阵不对称、函数端点值、离散空集;判空、行列边界与精度口径。
概念解释
- 退化维度。
- 越界目标。
- 特殊结构。
原理流程
- 判空维度。
- 单行单列走对应分支。
- 端点越界返回。
代码 / 图示
1×n / m×1 / 空
target < min / > max
常见误区
- 误区:空矩阵访问 [0][0];正解:先判行列。
- 误区:单行误用折线法;正解:退化为一维二分。
追问
- Q:全相同矩阵? A:等值命中或全部非目标。
- Q:浮点无根? A:返回约定值。
02.5.1.4-016 矩阵退化情形怎么处理?
一句话结论
单行退化为一维二分;单列同理;空矩阵直接返回;折线法在单行/单列时移动方向仍成立,但优先套一维模板避免边界错误。
概念解释
- 维度退化。
- 模板兼容。
- 边界安全。
原理流程
- 判断行列数。
- 单行单列套一维。
- 空返回默认。
代码 / 图示
rows=1 → 一维
cols=1 → 一维
常见误区
- 误区:退化矩阵折线越界;正解:先判维度。
- 误区:空矩阵换算下标;正解:先判长度。
追问
- Q:1×1 矩阵? A:单点比较。
- Q:非矩形矩阵? A:列宽不一致,不能统一映射。
02.5.1.4-017 矩阵二分常见错误有哪些?
一句话结论
形态误判直接一维二分、起点选错无法排除、行列换算除错列数、空矩阵未判、折线方向写反、第 K 小计数未利用有序;先判形态再选策略。
概念解释
- 形态。
- 起点与方向。
- 换算口径。
原理流程
- 核对行首尾衔接。
- 核对起点性质。
- 核对下标换算。
代码 / 图示
衔接 → 一维;不衔接 → 折线
常见误区
- 误区:把 LC 240 当 LC 74;正解:题目先读结构。
- 误区:折线法行/列移动方向反;正解:大移列小移行。
追问
- Q:怎么自测形态? A:比较每行尾与下行首。
- Q:计数错误导致第 K 小错位? A:核对每行 ≤ 个数。
02.5.1.4-018 二维与非数组二分复杂度怎么汇报?
一句话结论
全有序矩阵 O(log(mn));行列有序折线 O(m+n);第 K 小 O(计数代价 · log R);非数组按候选空间高度/轮次;空间多为 O(1)。
概念解释
- 形态时间。
- 计数代价。
- 辅助常数。
原理流程
- 标注矩阵规模。
- 选策略对应阶。
- 分列时间空间。
代码 / 图示
一维映射:O(log mn)
折线:O(m+n)
K 小:O(m log n · log R)
常见误区
- 误区:矩阵二分恒 O(log mn);正解:局部有序折线 O(m+n)。
- 误区:非数组不计比较代价;正解:函数求值计入。
追问
- Q:堆做法第 K 小? A:O(k log n),K 小更优。
- Q:空间占用? A:迭代 O(1)。
02.5.1.4-019 二维与非数组二分怎么和一维模板衔接?
一句话结论
先把候选空间映射成一维有序下标或数值区间,再套 02.5.1.1 区间不变量;映射转换是额外一步,比较与收缩方向仍遵循基础模板。
概念解释
- 空间映射。
- 模板复用。
- 方向一致。
原理流程
- 找有序维度。
- 映射到下标/值。
- 套基础二分。
代码 / 图示
矩阵 → 一维下标 → 基础模板
函数 → 值域 → 二分答案
常见误区
- 误区:映射后改变区间口径;正解:映射前后不变量一致。
- 误区:非数组另造模板;正解:折半排除通用。
追问
- Q:学本页前掌握什么? A:lower_bound 与区间边界。
- Q:映射失败怎么办? A:说明候选空间非有序,不能二分。
02.5.1.4-020 二维与非数组二分常见变体有哪些?
一句话结论
全有序矩阵搜索、行列有序折线搜索、矩阵第 K 小、二维峰值、单调函数求根、有序集合定位、BST 查找、区间归属;主线是有序候选空间 + 折半排除。
概念解释
- 框架:折半二分。
- 变体:候选空间不同。
- 场景包装。
原理流程
- 识别有序维度。
- 映射候选空间。
- 套模板判定。
代码 / 图示
矩阵 → 下标/行列
函数 → 值域
树 → 子树分支
常见误区
- 误区:变体脱离折半本质;正解:每次排除一半候选。
- 误区:无序空间硬二分;正解:先证明单调/有序。
追问
- Q:网格最短路? A:BFS,非二分,见 02.4.2.4。
- Q:矩阵旋转? A:原地反转,非二分,见 02.5.1.2-009。