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

1. 矩阵置零（Set Matrix Zeroes）

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

解题思路

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

步骤：

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

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

2. 遍历矩阵：

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

3. 根据标记置零：

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

4. 处理第一行和第一列：

   • 最后，根据 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 的矩阵，按螺旋顺序返回矩阵中的所有元素。

解题思路

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

具体步骤：

1. 定义边界：

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

2. 遍历顺序：

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

3. 终止条件：

   • 当结果列表的大小等于 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 度。你必须在原地（即不使用额外的二维数组）完成旋转。

解决思路

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

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

通过这两步操作，我们可以原地完成矩阵的 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) 时间复杂度内完成这个搜索。

解决思路

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

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

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

2. 这样，每次搜索都可以排除一行或一列，因此我们可以在 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;  // 未找到目标值
    }
}