罗罗编程学习记录
本页内容 展开查看

02.5.1.4 二维矩阵与非数组二分

所属:全栈开发面试题库 / 02 数据结构与算法 / 02.5 二分与排序 / 02.5.1 二分查找

02.5.1.4-001 二维有序矩阵有哪两种形态?

一句话结论

形态一:每行有序且下一行首元素 ≥ 上一行尾元素,可视为一维有序数组;形态二:行列各自有序但行间不保证衔接,需按行列排除;先判断属于哪种。

概念解释

  • 全矩阵有序。
  • 行列局部有序。
  • 排除策略不同。

原理流程

  1. 比较行首尾衔接。
  2. 全有序映射一维。
  3. 局部有序按行列收缩。

代码 / 图示

形态一:每行尾 ≤ 下行首
形态二:行升序、列升序,行间不衔接

常见误区

  • 误区:两种形态用同一模板;正解:先确认衔接关系。
  • 误区:行列有序即全局有序;正解:形态二不保证。

追问

  • 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) 空间。

概念解释

  • 一维映射。
  • 行列换算。
  • 普通二分。

原理流程

  1. 展平下标区间 [0, mn)。
  2. mid 换算行列。
  3. 比较收缩。

代码 / 示例

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) 空间;不能直接一维二分。

概念解释

  • 右上角:左小下大。
  • 行列排除。
  • 折线搜索。

原理流程

  1. 从右上开始。
  2. 大则列左移。
  3. 小则行下移。

代码 / 示例

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;前提是行优先展平且矩阵等宽;换算时注意列数常量。

概念解释

  • 行优先编号。
  • 整除与取模。
  • 等宽前提。

原理流程

  1. 展平按行排列。
  2. 乘列数加列号。
  3. 逆映射还原。

代码 / 图示

idx → (idx / cols, idx % cols)

常见误区

  • 误区:误用行数换算;正解:除列数。
  • 误区:列宽不一致;正解:等宽矩阵才适用。

追问

  • Q:列优先? A:idx = col*rows+row,口径对应。
  • Q:下标溢出? A:rows*cols 注意 int 范围。

02.5.1.4-005 右上角搜索法为什么能排除行列?

一句话结论

右上角元素是该行最大、该列最小;比 target 大则该行右侧无需再看(左移),比 target 小则该列上方无需再看(下移);每次排除一行或一列。

概念解释

  • 位置性质。
  • 单向排除。
  • 折线收敛。

原理流程

  1. 右上角行最大列最小。
  2. 大:排除当前行右侧。
  3. 小:排除当前列上方。

代码 / 图示

      ← 列
行 ↓  右上

常见误区

  • 误区:排除整行还是整列混淆;正解:大移列,小移行。
  • 误区:起点选错导致双向都无法排除;正解:选角部单调方向。

追问

  • Q:左下角对称版本? A:行最小列最大,方向镜像。
  • Q:什么矩阵不能用? A:行或列无序。

02.5.1.4-006 矩阵二分复杂度怎么算?

一句话结论

全有序一维映射 O(log(mn));行列有序折线法 O(m+n);每行二分 O(m log n);空间 O(1);按矩阵形态选策略。

概念解释

  • 形态决定策略。
  • 行列规模。
  • 辅助常数。

原理流程

  1. 判断矩阵形态。
  2. 统计行列规模。
  3. 标注时间空间。

代码 / 图示

全有序: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)。

概念解释

  • 二分答案。
  • 计数判定。
  • 行列有序辅助。

原理流程

  1. 值域在矩阵最小最大间。
  2. check 统计 ≤ mid 个数。
  3. 收敛第 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 二维峰值元素怎么找?

一句话结论

二维网格中峰值大于四邻居;可逐行二分找行内峰值列,再比较上下行该列值调整行方向;或按行/列折半;局部性质可二分排除一侧。

概念解释

  • 四邻居。
  • 行列调整。
  • 局部最大。

原理流程

  1. 取行内最大列。
  2. 与上下比较。
  3. 高处行继续。

代码 / 图示

当前格 ≥ 上下 → 峰值
下方更大 → 下移行

常见误区

  • 误区:全局有序才找峰值;正解:局部比较可排除侧。
  • 误区:只看左右邻居;正解:二维含上下。

追问

  • Q:LC 162 一维峰值? A:见 02.5.1.1-013 思路。
  • Q:边界格邻居? A:缺邻居按比较处理。

02.5.1.4-009 二维矩阵遍历与二分怎么衔接?

一句话结论

先判断矩阵有序形态,全有序套一维二分;局部有序套行列折线;需要统计计数时结合每行二分;二维前缀和等遍历问题不属于二分。

概念解释

  • 形态判断。
  • 策略选择。
  • 边界区分。

原理流程

  1. 看行首尾衔接。
  2. 选一维/折线。
  3. 计数再二分答案。

代码 / 图示

衔接 → 一维二分
不衔接 → 折线

常见误区

  • 误区:所有矩阵题都二分;正解:无序遍历用 DFS/BFS。
  • 误区:折线法用于全有序;正解:全有序二分更快。

追问

  • Q:岛屿遍历? A:DFS/BFS,见 02.4.2.1。
  • Q:矩阵求和? A:前缀和,见 02.2.1。

02.5.1.4-010 非数组的二分能用在什么上?

一句话结论

只要候选空间在某个有序维度上单调,即可二分:整数答案、单调函数求根、离散有序集合、区间定位、BST 查找;本质都是折半排除一半候选。

概念解释

  • 有序候选空间。
  • 判定比较。
  • 折半通用。

原理流程

  1. 找有序维度。
  2. 中点判定。
  3. 排除一侧。

代码 / 图示

函数 f(x) 单调 → 求零点
BST 按值 → 走子树

常见误区

  • 误区:二分只能用于数组;正解:单调候选空间均可。
  • 误区:树结构上二分按数组下标;正解:按树分支比较。

追问

  • Q:BST 查找复杂度? A:O(h),见 02.4.1.2。
  • Q:函数求根? A:二分零点,需单调连续。

02.5.1.4-011 单调函数怎么用二分求根?

一句话结论

函数单调连续,零点两侧符号相反;中点比较符号(或与目标值比较),缩小区间到精度;整数根用整数二分,浮点根按精度迭代。

概念解释

  • 单调连续。
  • 符号分界。
  • 精度收敛。

原理流程

  1. 找符号相反区间。
  2. 中点算值比较。
  3. 收缩到精度。

代码 / 图示

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) 访问,不能高效二分;映射到下标后套模板。

概念解释

  • 随机访问。
  • 排名下标。
  • 结构限制。

原理流程

  1. 确认可随机访问。
  2. 下标二分。
  3. 定位元素。

代码 / 图示

有序数组:可二分
有序链表:线性访问

常见误区

  • 误区:有序链表二分;正解:访问中点需 O(n)。
  • 误区:集合有重复未排序;正解:先排序。

追问

  • Q:TreeSet 查找? A:红黑树 O(log n),非数组二分。
  • Q:排名查询? A:平衡树/下标数组。

02.5.1.4-013 区间定位类二分是什么?

一句话结论

候选是区间(如插入位置、区间覆盖归属),二分找到区间边界;与 lower_bound 同源,返回左/右边界下标;常配合区间合并问题。

概念解释

  • 边界定位。
  • 区间归属。
  • 上下界模板。

原理流程

  1. 区间有序排列。
  2. 二分定位边界。
  3. 返回归属区间。

代码 / 图示

[1,3) [3,5) [5,8) → 二分找所属段

常见误区

  • 误区:区间端点重叠归属写错;正解:开闭口径统一。
  • 误区:线性扫描区间;正解:有序可二分。

追问

  • Q:合并区间? A:排序贪心,见 02.2.1。
  • Q:日程安排? A:有序区间二分定位。

02.5.1.4-014 BST 上的二分是什么思路?

一句话结论

BST 按值比较:小走左子树、大走右子树;每次排除一棵子树,O(h);与数组二分同属折半思想,但比较对象是节点值而非下标。

概念解释

  • 值比较。
  • 子树排除。
  • 树高口径。

原理流程

  1. 当前节点比较。
  2. 小走左,大走右。
  3. 命中或到空。

代码 / 图示

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. 判空维度。
  2. 单行单列走对应分支。
  3. 端点越界返回。

代码 / 图示

1×n / m×1 / 空
target < min / > max

常见误区

  • 误区:空矩阵访问 [0][0];正解:先判行列。
  • 误区:单行误用折线法;正解:退化为一维二分。

追问

  • Q:全相同矩阵? A:等值命中或全部非目标。
  • Q:浮点无根? A:返回约定值。

02.5.1.4-016 矩阵退化情形怎么处理?

一句话结论

单行退化为一维二分;单列同理;空矩阵直接返回;折线法在单行/单列时移动方向仍成立,但优先套一维模板避免边界错误。

概念解释

  • 维度退化。
  • 模板兼容。
  • 边界安全。

原理流程

  1. 判断行列数。
  2. 单行单列套一维。
  3. 空返回默认。

代码 / 图示

rows=1 → 一维
cols=1 → 一维

常见误区

  • 误区:退化矩阵折线越界;正解:先判维度。
  • 误区:空矩阵换算下标;正解:先判长度。

追问

  • Q:1×1 矩阵? A:单点比较。
  • Q:非矩形矩阵? A:列宽不一致,不能统一映射。

02.5.1.4-017 矩阵二分常见错误有哪些?

一句话结论

形态误判直接一维二分、起点选错无法排除、行列换算除错列数、空矩阵未判、折线方向写反、第 K 小计数未利用有序;先判形态再选策略。

概念解释

  • 形态。
  • 起点与方向。
  • 换算口径。

原理流程

  1. 核对行首尾衔接。
  2. 核对起点性质。
  3. 核对下标换算。

代码 / 图示

衔接 → 一维;不衔接 → 折线

常见误区

  • 误区:把 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)。

概念解释

  • 形态时间。
  • 计数代价。
  • 辅助常数。

原理流程

  1. 标注矩阵规模。
  2. 选策略对应阶。
  3. 分列时间空间。

代码 / 图示

一维映射: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 区间不变量;映射转换是额外一步,比较与收缩方向仍遵循基础模板。

概念解释

  • 空间映射。
  • 模板复用。
  • 方向一致。

原理流程

  1. 找有序维度。
  2. 映射到下标/值。
  3. 套基础二分。

代码 / 图示

矩阵 → 一维下标 → 基础模板
函数 → 值域 → 二分答案

常见误区

  • 误区:映射后改变区间口径;正解:映射前后不变量一致。
  • 误区:非数组另造模板;正解:折半排除通用。

追问

  • Q:学本页前掌握什么? A:lower_bound 与区间边界。
  • Q:映射失败怎么办? A:说明候选空间非有序,不能二分。

02.5.1.4-020 二维与非数组二分常见变体有哪些?

一句话结论

全有序矩阵搜索、行列有序折线搜索、矩阵第 K 小、二维峰值、单调函数求根、有序集合定位、BST 查找、区间归属;主线是有序候选空间 + 折半排除。

概念解释

  • 框架:折半二分。
  • 变体:候选空间不同。
  • 场景包装。

原理流程

  1. 识别有序维度。
  2. 映射候选空间。
  3. 套模板判定。

代码 / 图示

矩阵 → 下标/行列
函数 → 值域
树 → 子树分支

常见误区

  • 误区:变体脱离折半本质;正解:每次排除一半候选。
  • 误区:无序空间硬二分;正解:先证明单调/有序。

追问

  • Q:网格最短路? A:BFS,非二分,见 02.4.2.4。
  • Q:矩阵旋转? A:原地反转,非二分,见 02.5.1.2-009。