LeetCode Hot100----06-矩阵篇,包含多种方法，详细思路与代码，让你一篇文章看懂所有！
06--------------矩阵
目录
06--------------矩阵
1.73. 矩阵置零
解决方案一：集合标记法（O (m+n) 空间）
解决方案二：原地标记法（O (1) 空间）
2.54. 螺旋矩阵
1.核心思路：按层遍历
代码实现
复杂度分析
执行流程示例
关键点总结
与向左 / 向上遍历的对比
方法2：模拟
核心思路
关键逻辑解析
补充-------------方向数组 directions 是一种高效表示移动方向的方式
3.48. 旋转图像
方法一：两次翻转法（推荐）
方法二：使用辅助数组
方法三：分圈旋转法：矩阵顺时针旋转 90 度的核心逻辑
4.240. 搜索二维矩阵 II
方法一：直接查找
方法二：二分查找
方法三：搜索二叉树查找：
1.73. 矩阵置零
给定一个 *m* x *n* 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法(处理一个数时，可能会影响到未处理的数，最直接的方法就是创建额外空间来记录所要变更的数据------矩阵或者2个数组)。而原地算法，就有思考如何利用自身数据进行标记。。
进阶：
-
一个直观的解决方案是使用
O(*m**n*)的额外空间，但这并不是一个好的解决方案。 -
一个简单的改进方案是使用
O(*m* + *n*)的额外空间，但这仍然不是最好的解决方案。 -
你能想出一个仅使用常量空间的解决方案吗
首先，我需要思考如何在不使用额外二维数组的情况下解决这个问题。通常有几种方法可以考虑：
-
使用两个集合分别记录需要置零的行和列（i,j），然后遍历矩阵置零
-
空间复杂度：O (m+n)
-
这不是最优的 O (1) 空间复杂度解法，但可以作为基础解法
-
-
使用矩阵的第一行和第一列作为标记数组
-
空间复杂度：O (1)
-
这是最优解法，我将重点讲解这种方法
-
解决方案一：集合标记法（O (m+n) 空间）
class Solution { public void setZeroes(int[][] matrix) { int m = matrix.length; int n = matrix[0].length; // 记录需要置零的行和列 Set rows = new HashSet(); Set cols = new HashSet(); // 遍历矩阵，记录0的位置 for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (matrix[i][j] == 0) { rows.add(i); cols.add(j); } } } // 将记录的行和列置零 for (int row : rows) { for (int j = 0; j < n; j++) { matrix[row][j] = 0; } } for (int col : cols) { for (int i = 0; i < m; i++) { matrix[i][col] = 0; } } }}
解决方案二：原地标记法（O (1) 空间）
class Solution { public void setZeroes(int[][] matrix) { int m = matrix.length; int n = matrix[0].length; boolean firstRowHasZero = false; boolean firstColHasZero = false; // 检查第一行是否有0 for (int j = 0; j < n; j++) { if (matrix[0][j] == 0) { firstRowHasZero = true; break; } } // 检查第一列是否有0 for (int i = 0; i < m; i++) { if (matrix[i][0] == 0) { firstColHasZero = true; break; } } // 使用第一行和第一列作为标记数组 for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { if (matrix[i][j] == 0) { matrix[i][0] = 0; // 标记第i行需要置零 matrix[0][j] = 0; // 标记第j列需要置零 } } } // 根据第一列的标记，置零相应的行 for (int i = 1; i < m; i++) { if (matrix[i][0] == 0) { for (int j = 1; j < n; j++) { matrix[i][j] = 0; } } } // 根据第一行的标记，置零相应的列 for (int j = 1; j < n; j++) { if (matrix[0][j] == 0) { for (int i = 1; i < m; i++) { matrix[i][j] = 0; } } } // 处理第一行和第一列 if (firstRowHasZero) { for (int j = 0; j < n; j++) { matrix[0][j] = 0; } } if (firstColHasZero) { for (int i = 0; i < m; i++) { matrix[i][0] = 0; } } }}
算法解析
第二种方案是最优解，核心思想是利用矩阵的第一行和第一列作为标记数组，避免使用额外空间：
-
标记阶段：
-
首先检查第一行和第一列是否有 0，单独记录（因为它们将作为标记数组，需要特殊处理）
-
从第二行第二列开始遍历矩阵，若元素为 0，则在对应的第一行和第一列位置标记
-
-
置零阶段：
-
根据第一列的标记，置零相应的行
-
根据第一行的标记，置零相应的列
-
最后处理第一行和第一列的置零（使用之前记录的标记）
-
复杂度分析
-
时间复杂度：O (m×n)，需要两次遍历矩阵
-
空间复杂度：O (1)，仅使用常数额外空间
执行示例
以输入矩阵 [[1,1,1],[1,0,1],[1,1,1]] 为例：
-
发现 (1,1) 位置为 0，标记第一行 (0,1) 和第一列 (1,0) 为 0
-
根据标记，将第 1 行和第 1 列全部置 0
-
最终结果为 [[1,0,1],[0,0,0],[1,0,1]]
这种原地标记法充分利用了矩阵本身的空间作为标记，是解决此类问题的经典方法，满足题目对原地算法的要求。
2.54. 螺旋矩阵
给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]输出：[1,2,3,6,9,8,7,4,5]
1.核心思路：按层遍历
从矩阵的最外层开始，按右→下→左→上的顺序逐层遍历，每遍历完一层后，向内收缩边界。具体步骤：
-
初始化边界：定义上下左右四个边界
top,bottom,left,right。 -
循环遍历：
-
向右：从
left到right遍历当前顶层行。 -
向下：从
top+1到bottom遍历当前最右列。 -
向左（若存在未遍历的行）：从
right-1到left遍历当前底层行。 -
向上（若存在未遍历的列）：从
bottom-1到top+1遍历当前最左列。
-
-
收缩边界：每遍历完一层，更新边界（
top++,bottom--,left++,right--），继续遍历下一层。
代码实现
class Solution { public List spiralOrder(int[][] matrix) { List result = new ArrayList(); if (matrix == null || matrix.length == 0) return result; int m = matrix.length; // 行数 int n = matrix[0].length; // 列数 int top = 0, bottom = m - 1, left = 0, right = n - 1; while (top <= bottom && left <= right) { // 向右遍历顶层行 for (int j = left; j <= right; j++) { result.add(matrix[top][j]); } top++; // 向下遍历最右列 for (int i = top; i <= bottom; i++) { result.add(matrix[i][right]); } right--; // 若存在未遍历的行，向左遍历底层行 if (top = left; j--) { result.add(matrix[bottom][j]); } bottom--; } // 若存在未遍历的列，向上遍历最左列 if (left = top; i--) { result.add(matrix[i][left]); } left++; } } return result; }}
复杂度分析
-
时间复杂度：O (m×n)，需遍历矩阵中的每个元素一次。
-
空间复杂度：O (1)，仅使用常数级额外空间（不考虑结果列表的空间）。
执行流程示例
以矩阵 [[1,2,3],[4,5,6],[7,8,9]] 为例：
-
第一层遍历：
-
右：遍历
[1,2,3]，top++→top=1。 -
下：遍历
[6,9]，right--→right=1。 -
左：遍历
[8,7]，bottom--→bottom=1。 -
上：遍历
[4]，left++→left=1。
-
-
第二层遍历：
-
右：遍历
[5]，top++→top=2，结束循环。
-
最终结果：[1,2,3,6,9,8,7,4,5]。
关键点总结
-
边界处理：每次遍历后更新边界，并在每次循环开始时检查是否越界（
top <= bottom && left <= right）。 -
方向顺序：严格按右→下→左→上的顺序遍历，确保不重复、不遗漏。
-
特殊情况：当矩阵为单行或单列时，通过条件判断（
top <= bottom和left <= right）避免重复遍历。（也可以通过结果集长度作为终止条件）
该方法通过逐层收缩边界，简洁高效地实现了螺旋遍历，适用于任意大小的矩阵。
注意：在螺旋矩阵遍历中，向右（顶层行）和向下（最右列）的遍历被认为是 “安全” 的：
向右：进入循环时，top <= bottom 和 left <= right 已被外层 while 条件保证（while (top <= bottom && left <= right)），因此 top 行、left 到 right 列一定存在。
向下：同上，但是因为top++,此时可能出现top>bottom, 但向下遍历的条件是top<=bottom,所以如果越界来，不会执行。
// 向下遍历最右列 for (int i = top; i <= bottom; i++)
与向左 / 向上遍历的对比
[left, right] 和 [top, bottom] 内。top <= bottom 或 left <= right）top++, right--），可能导致行 / 列边界交叉，需额外检查避免越界。方法2：模拟
核心思路
-
路径模拟：从矩阵左上角开始，按右→下→左→上的顺序循环移动，遇到边界或已访问元素时转向。
-
方向控制：使用方向数组
directions表示四个方向，通过directionIndex循环切换方向（右→下→左→上→右→...）。 -
访问标记：维护一个与原矩阵大小相同的
visited数组，记录每个位置是否被访问过，避免重复访问。 -
终止条件：当遍历的元素数量达到矩阵总元素数时结束。
关键逻辑解析
-
方向切换机制：
-
方向数组按 右→下→左→上 顺序排列，当需要转向时，通过
directionIndex = (directionIndex + 1) % 4实现循环切换。例如，向右移动遇到边界后切换为向下，向下遇到边界后切换为向左，依此类推。
-
-
边界与重复访问判断：
-
越界判断：通过
nextRow < 0、nextRow >= rows、nextColumn < 0、nextColumn >= columns检查下一个位置是否超出矩阵范围。 -
重复访问判断：通过
visited[nextRow][nextColumn]检查该位置是否已被访问，避免重复添加元素。
-
判断路径是否进入之前访问过的位置需要使用一个与输入矩阵大小相同的辅助矩阵 visited，其中的每个元素表示该位置是否被访问过。当一个元素被访问时，将 visited 中的对应位置的元素设为已访问。
如何判断路径是否结束？由于矩阵中的每个元素都被访问一次，因此路径的长度即为矩阵中的元素数量，当路径的长度达到矩阵中的元素数量时即为完整路径，将该路径返回。
class Solution { public List spiralOrder(int[][] matrix) { // 初始化结果列表和边界检查List order = new ArrayList();if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return order;// 获取矩阵尺寸并初始化访问标记数组int rows = matrix.length, columns = matrix[0].length;boolean[][] visited = new boolean[rows][columns];int total = rows * columns;// 初始位置和方向int row = 0, column = 0;int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 右、下、左、上int directionIndex = 0;// 遍历所有元素for (int i = 0; i < total; i++) { // 将当前元素加入结果列表并标记为已访问 order.add(matrix[row][column]); visited[row][column] = true; // 计算下一个位置 int nextRow = row + directions[directionIndex][0]; int nextColumn = column + directions[directionIndex][1]; // 判断是否需要转向（越界或已访问） if (nextRow = rows || nextColumn = columns || visited[nextRow][nextColumn]) { directionIndex = (directionIndex + 1) % 4; // 顺时针切换方向 } // 更新当前位置为新方向的下一个位置 row += directions[directionIndex][0]; column += directions[directionIndex][1];} return order; }}
补充-------------方向数组 directions 是一种高效表示移动方向的方式
一、方向数组的定义与作用
-
数组结构
方向数组通常定义为包含四个元素的二维数组，每个元素表示一个方向的行增量和列增量，例如：
directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]
-
[0, 1]：向右移动（行不变，列 + 1）。 -
[1, 0]：向下移动（行 + 1，列不变）。 -
[0, -1]：向左移动（行不变，列 - 1）。 -
[-1, 0]：向上移动（行 - 1，列不变）。
-
作用
通过方向数组，可将 “方向切换” 转化为数组索引的循环更新，避免重复编写方向判断逻辑，使代码更简洁、易维护。
二、方向数组的使用场景
以螺旋矩阵遍历为例，方向数组的典型应用流程如下：
-
初始化方向索引：
directionIndex = 0（初始方向为向右）。 -
计算下一个位置
int nextRow = row + directions[directionIndex][0];int nextColumn = column + directions[directionIndex][1];
-
方向切换：当遇到边界或已访问位置时，通过
directionIndex = (directionIndex + 1) % 4顺时针切换方向，确保按 右→下→左→上→右 的顺序循环。
3.48. 旋转图像
给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]输出：[[7,4,1],[8,5,2],[9,6,3]]
方法一：两次翻转法（推荐）
-
先水平翻转矩阵：将矩阵的每一行进行上下交换，即第 i 行与第 n-1-i 行交换。
-
再沿主对角线翻转矩阵：将矩阵中每个元素 matrix i 与 matrix j 交换。
这两次翻转操作的组合等效于顺时针旋转 90 度，且不需要额外空间。
class Solution { public void rotate(int[][] matrix) { int n = matrix.length; // 水平翻转 for (int i = 0; i < n / 2; i++) { for (int j = 0; j < n; j++) { int temp = matrix[i][j]; matrix[i][j] = matrix[n - 1 - i][j]; matrix[n - 1 - i][j] = temp; } } // 主对角线翻转 for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { int temp = matrix[i][j]; matrix[i][j] = matrix[j][i]; matrix[j][i] = temp; } } }}
方法二：使用辅助数组
对于矩阵中第 i 行的第 j 个元素，在旋转后，它出现在倒数第 i 列的第 j 个位置。
**matrix_new[j][n - i - 1] = matrix[i][j];**
之后再
matrix[i][j] = matrix_new[i][j];
方法三：分圈旋转法：矩阵顺时针旋转 90 度的核心逻辑
一、核心思想：将矩阵分解为同心环处理
n×n 的矩阵可看作由多个同心正方形环组成，最外层为第 1 圈，向内依次为第 2 圈、第 3 圈…… 直至矩阵中心。分圈旋转法通过逐层处理每个环，将环上的元素按顺时针方向移动到目标位置，最终实现整体旋转。
二、环的范围确定
-
对于第 i 层环（从 0 开始计数）：
-
上边界：
i -
下边界：
n-1-i -
左边界：
i -
右边界：
n-1-i
-
-
当
i >= n/2时，无需继续处理（此时已覆盖所有环）。
三、单环元素的顺时针交换逻辑
以 3×3 矩阵的最外层环（i=0）为例，环上的元素需按以下规则移动
原位置（上边） → 目标位置（右边） 原位置（右边） → 目标位置（下边） 原位置（下边） → 目标位置（左边） 原位置（左边） → 目标位置（上边）
具体来说，对于环上的每个位置 (i, j)（j 从 i 到 n-1-i），四个位置的交换关系为：
matrix[i][j] ↔ matrix[j][n-1-i] （上边→右边） matrix[j][n-1-i] ↔ matrix[n-1-i][n-1-j] （右边→下边） matrix[n-1-i][n-1-j] ↔ matrix[n-1-j][i] （下边→左边） matrix[n-1-j][i] ↔ matrix[i][j] （左边→上边）
为避免覆盖，需用临时变量暂存第一个位置的值，按顺序交换。
示例： 对于矩阵：
[1,2,3][4,5,6][7,8,9]
-
处理最外层环：
-
交换元素：1→3→9→7→1
-
交换元素：2→6→8→4→2 得到：
[7,4,1][8,5,2][9,6,3]
class Solution { public void rotate(int[][] matrix) { int n = matrix.length; // 处理第i层环，i从0到n/2-1 for (int i = 0; i < n / 2; i++) { // 处理环的上边，j从i到n-1-i for (int j = i; j < n - 1 - i; j++) { int temp = matrix[i][j]; // 按顺序交换四个位置 matrix[i][j] = matrix[n - 1 - j][i]; matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j]; matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i]; matrix[j][n - 1 - i] = temp; } } }}4.240. 搜索二维矩阵 II
编写一个高效的算法来搜索
*m* x *n*矩阵matrix中的一个目标值target。该矩阵具有以下特性：-
每行的元素从左到右升序排列。
-
每列的元素从上到下升序排列。
示例 1：
输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5输出：true
-
方法一：直接查找
思路与算法:我们直接遍历整个矩阵 matrix，判断 target 是否出现即可。
class Solution { public boolean searchMatrix(int[][] matrix, int target) { for (int[] row : matrix) { for (int element : row) { if (element == target) { return true; } } } return false; }}
复杂度分析
时间复杂度：O(mn)。
空间复杂度：O(1)。
方法二：二分查找
思路与算法:由于矩阵 matrix 中每一行的元素都是升序排列的，因此我们可以对每一行都使用一次二分查找，判断 target 是否在该行中，从而判断 target 是否出现。
class Solution { public boolean searchMatrix(int[][] matrix, int target) { for (int[] row : matrix) { int index = search(row, target); if (index >= 0) { return true; } } return false; }public int search(int[] nums, int target) { int low = 0, high = nums.length - 1; while (low target) { high = mid - 1; } else { low = mid + 1; } } return -1;}}
复杂度分析
-
时间复杂度：O(mlogn)。对一行使用二分查找的时间复杂度为 O(logn)，最多需要进行 m 次二分查找。
-
空间复杂度：O(1)。
方法三：搜索二叉树查找：
核心搜索策略：从右上角出发的线性搜索
-
起点选择：选择矩阵的右上角元素
matrix[0][n-1]作为搜索起点。-
该位置的特性：左侧元素更小，下侧元素更大，便于根据目标值调整搜索方向。
-
-
方向调整逻辑：
-
若
target == matrix[i][j]：直接找到目标，返回true。 -
若
target < matrix[i][j]：目标值不可能在当前行的右侧（右侧元素更大），向左移动一列（j--）。 -
若
target > matrix[i][j]：目标值不可能在当前列的上侧（上侧元素更小），向下移动一行（i++）。
-
-
终止条件：当行索引
i超出矩阵行数或列索引j小于 0 时，说明矩阵中无目标值，返回false。
示例解析
以矩阵 [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]] 为例，搜索 target=16：
-
初始位置：
(0,4)（元素 15），16 > 15，向下移动到(1,4)（19）。 -
16 < 19，向左移动到(1,3)（12），16 > 12，向下移动到(2,3)（16），找到目标，返回true。
class Solution { public boolean searchMatrix(int[][] matrix, int target) { if (matrix == null || matrix.length == 0 || matrix[0].length == 0) { return false; } int m = matrix.length; int n = matrix[0].length; int i = 0, j = n - 1; // 从右上角开始搜索 while (i = 0) { if (matrix[i][j] == target) { return true; } else if (matrix[i][j] > target) { j--; // 目标值更小，向左移动 } else { i++; // 目标值更大，向下移动 } } return false; }}
复杂度分析
-
时间复杂度：O (m + n)，其中
m和n分别为矩阵的行数和列数。每次移动要么行加 1，要么列减 1，最多移动m + n次。 -
空间复杂度：O (1)，仅使用常数级额外空间。
策略优势
-
高效性：相比遍历矩阵（O (mn)）或对每行二分搜索（O (m log n)），该方法在大多数情况下更优，尤其当矩阵接近正方形时（m ≈ n）。
-
逻辑性：利用矩阵的行列有序性，通过 “剪枝” 快速缩小搜索范围，无需复杂计算。
-
扩展性：若矩阵改为 “每行从右到左升序、每列从下到上升序”，可选择左下角作为起点，按类似逻辑搜索。
变种思路：从左下角出发
若选择矩阵的左下角元素 matrix[m-1][0] 作为起点：
-
若
target == matrix[i][j]：返回true。 -
若
target < matrix[i][j]：向上移动一行（i--）。 -
若
target > matrix[i][j]：向右移动一列（j++）。 逻辑本质与右上角搜索一致，时间复杂度相同。
总结：由于二维的复杂性，所有总体逻辑不算复杂，主要考察编程熟练度。
