跳到主要内容

矩阵算法练习

矩阵类题目通常是对多维数组的操作。主要涉及模拟、图像轴对称/中心对称关系，或特定的路径搜索。

73. 矩阵置零 (Set Matrix Zeroes)​

题目描述​

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

解题思路​

利用矩阵的第一行和第一列作为标记位。

  1. 预先记录第一行和第一列是否本来就有 0。
  2. 遍历内部元素，如果为 0，标记对应的第一行和第一列。
  3. 根据标记对内部元素置零。
  4. 最后处理第一行和第一列。

Java 代码实现​

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean row0 = false, col0 = false;
        for (int i = 0; i < m; i++) if (matrix[i][0] == 0) col0 = true;
        for (int j = 0; j < n; j++) if (matrix[0][j] == 0) row0 = true;
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0; matrix[0][j] = 0;
                }
            }
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) matrix[i][j] = 0;
            }
        }
        if (col0) for (int i = 0; i < m; i++) matrix[i][0] = 0;
        if (row0) for (int j = 0; j < n; j++) matrix[0][j] = 0;
    }
}

54. 螺旋矩阵 (Spiral Matrix)​

题目描述​

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

解题思路​

设定四个边界：upper, lower, left, right。通过不断在边界内向右、向下、向左、向上遍历，并更新边界，直至元素全部加入结果列表。

Java 代码实现​

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        if (matrix.length == 0) return res;
        int upper = 0, lower = matrix.length - 1;
        int left = 0, right = matrix[0].length - 1;
        while (true) {
            for (int j = left; j <= right; j++) res.add(matrix[upper][j]);
            if (++upper > lower) break;
            for (int i = upper; i <= lower; i++) res.add(matrix[i][right]);
            if (--right < left) break;
            for (int j = right; j >= left; j--) res.add(matrix[lower][j]);
            if (--lower < upper) break;
            for (int i = lower; i >= upper; i--) res.add(matrix[i][left]);
            if (++left > right) break;
        }
        return res;
    }
}

48. 旋转图像 (Rotate Image)​

题目描述​

给定一个 n x n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。你必须在 原地 旋转图像。

解题思路​

顺时针旋转 90 度等价于：先进行主对角线转置（翻转），再进行左右翻转。

Java 代码实现​

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        // 转置
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = tmp;
            }
        }
        // 每一行左右翻转
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n / 2; j++) {
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[i][n - 1 - j];
                matrix[i][n - 1 - j] = tmp;
            }
        }
    }
}

240. 搜索二维矩阵 II (Search a 2d Matrix II)​

题目描述​

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：每行的元素从左到右升序排列，每列的元素从上到下升序排列。

解题思路​

从右上角开始搜索。右上角的数是该排的最大、该列的最小。

  1. 如果 matrix[i][j] == target，返回。
  2. 如果 matrix[i][j] > target，说明该列下面的数也由于排序一定更大，向左移动。
  3. 如果 matrix[i][j] < target，说明该排左边的数一定更小，向下移动。

Java 代码实现​

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int i = 0, j = matrix[0].length - 1;
        while (i < matrix.length && j >= 0) {
            if (matrix[i][j] == target) return true;
            if (matrix[i][j] > target) j--;
            else i++;
        }
        return false;
    }
}