【LeetCodeHot100矩阵】矩阵置零、螺旋矩阵、旋转图像、搜索二维矩阵II

矩阵 1. 矩阵置零（Set Matrix Zeroes）解题思路步骤： 代码实现 2. 螺旋矩阵（Spiral Matrix）解题思路具体步骤： 代码实现 3. 旋转矩阵 90 度解决思路代码实现 5. 搜索二维矩阵中的目标值解决思路代码实现

1. 矩阵置零（Set Matrix Zeroes）

给定一个 m x n 的矩阵 matrix，如果一个元素是 0，则将其所在的整行和整列都设置为 0。你需要 原地 修改输入矩阵，不能 使用额外的矩阵。

解题思路

要实现原地修改矩阵，可以借助矩阵的第一行和第一列作为辅助存储，记录哪些行和列需要被置零。

步骤：

检查第一行和第一列是否包含零：

由于我们使用第一行和第一列来标记其他行列是否需要置零，所以需要先检查第一行和第一列是否包含零。如果包含零，我们分别用 rowFlag 和 colFlag 进行标记。

遍历矩阵：

从第二行第二列开始遍历整个矩阵。如果某个元素是零，则将其所在的第一行和第一列对应的元素设为零，表示该行和该列后续需要置零。

根据标记置零：

再次遍历矩阵，根据第一行和第一列的标记，将需要置零的位置修改为零。

处理第一行和第一列：

最后，根据 rowFlag 和 colFlag 的值，单独处理第一行和第一列的置零问题。 代码实现 class Solution { public void setZeroes(int[][] matrix) { int n = matrix[0].length; // 列数 int m = matrix.length; // 行数 boolean colFlag = false, rowFlag = false; // 检查第一列是否包含零 for (int i = 0; i < m; i++) { if (matrix[i][0] == 0) { colFlag = true; break; } } // 检查第一行是否包含零 for (int j = 0; j < n; j++) { if (matrix[0][j] == 0) { rowFlag = true; break; } } // 遍历矩阵，使用第一行和第一列标记零的位置 for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { if (matrix[i][j] == 0) { matrix[0][j] = 0; // 标记该列 matrix[i][0] = 0; // 标记该行 } } } // 根据第一行和第一列的标记进行置零 for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { if (matrix[0][j] == 0 || matrix[i][0] == 0) { matrix[i][j] = 0; } } } // 处理第一列置零 if (colFlag) { for (int i = 0; i < m; i++) { matrix[i][0] = 0; } } // 处理第一行置零 if (rowFlag) { for (int j = 0; j < n; j++) { matrix[0][j] = 0; } } } } 2. 螺旋矩阵（Spiral Matrix）

给定一个 m x n 的矩阵，按螺旋顺序返回矩阵中的所有元素。

解题思路

我们可以模拟螺旋遍历的过程，使用四个边界来控制当前遍历的范围。随着遍历的进行，逐步缩小这些边界，直到遍历完成整个矩阵。

具体步骤：

定义边界：

l 表示左边界，初始为 0。r 表示右边界，初始为 m-1。t 表示上边界，初始为 0。b 表示下边界，初始为 n-1。

遍历顺序：

按照螺旋顺序：从左到右遍历上边界，向下遍历右边界，从右到左遍历下边界，向上遍历左边界。每次遍历完一条边后，更新相应的边界。

终止条件：

当结果列表的大小等于 m * n 时，遍历结束。 代码实现 class Solution { public List<Integer> spiralOrder(int[][] matrix) { List<Integer> list = new ArrayList<>(); int m = matrix[0].length, n = matrix.length; int l = 0, r = m - 1, t = 0, b = n - 1; // 继续遍历直到所有元素都被加入列表 while (list.size() < m * n) { // 从左到右遍历上边界 for (int i = l; i <= r; i++) { if (list.size() == m * n) break; list.add(matrix[t][i]); } t++; // 缩小上边界的范围 // 从上到下遍历右边界 for (int i = t; i <= b; i++) { if (list.size() == m * n) break; list.add(matrix[i][r]); } r--; // 缩小右边界的范围 // 从右到左遍历下边界 for (int i = r; i >= l; i--) { if (list.size() == m * n) break; list.add(matrix[b][i]); } b--; // 缩小下边界的范围 // 从下到上遍历左边界 for (int i = b; i >= t; i--) { if (list.size() == m * n) break; list.add(matrix[i][l]); } l++; // 缩小左边界的范围 } return list; } } 3. 旋转矩阵 90 度

给定一个 n x n 的二维矩阵，编写一个函数将该矩阵顺时针旋转 90 度。你必须在原地（即不使用额外的二维数组）完成旋转。

解决思路

该问题可以通过两步操作实现：

水平翻转：将矩阵上下翻转。对角线翻转：再将矩阵沿主对角线进行翻转。

通过这两步操作，我们可以原地完成矩阵的 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-i-1][j]; matrix[n-i-1][j] = temp; } } // 再沿着对角线翻转 for(int i = 0; i < n; i++) { for(int j = 0; j < i; j++) { int temp = matrix[i][j]; matrix[i][j] = matrix[j][i]; matrix[j][i] = temp; } } } } 5. 搜索二维矩阵中的目标值

给定一个 m x n 的矩阵 matrix 和一个目标值 target，编写一个函数判断目标值是否在矩阵中。矩阵中的元素按照以下规则排序：

每行的元素从左到右升序排列。每列的元素从上到下升序排列。

你需要在 O(m + n) 时间复杂度内完成这个搜索。

解决思路

由于矩阵的元素是按行升序、按列升序排列的，我们可以使用一种特殊的搜索方法：

从矩阵的右上角开始搜索：

如果当前元素等于目标值，直接返回 true。如果当前元素大于目标值，说明目标值可能在该元素的左边（向左移动一列）。如果当前元素小于目标值，说明目标值可能在该元素的下方（向下移动一行）。

这样，每次搜索都可以排除一行或一列，因此我们可以在 O(m + n) 时间复杂度内完成搜索。

代码实现 class Solution { public boolean searchMatrix(int[][] matrix, int target) { int m = matrix.length, n = matrix[0].length; int x = 0, y = n - 1; // 从右上角开始搜索 while (x < m && y >= 0) { // 当索引仍在矩阵范围内 if (matrix[x][y] == target) { return true; // 找到目标值 } else if (matrix[x][y] > target) { y--; // 当前值大于目标值，向左移动 } else { x++; // 当前值小于目标值，向下移动 } } return false; // 未找到目标值 } }