跳到主要内容

矩阵操作

问题​

Java 中矩阵相关的常见算法题有哪些？

答案​

螺旋矩阵（LeetCode 54）​

边界收缩法
public List<Integer> spiralOrder(int[][] matrix) {
    List<Integer> result = new ArrayList<>();
    int top = 0, bottom = matrix.length - 1;
    int left = 0, right = matrix[0].length - 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 <= bottom) {
            for (int j = right; j >= left; j--) result.add(matrix[bottom][j]); // ←
            bottom--;
        }
        if (left <= right) {
            for (int i = bottom; i >= top; i--) result.add(matrix[i][left]);   // ↑
            left++;
        }
    }
    return result;
}

搜索二维矩阵 II（LeetCode 240）​

从右上角出发，类似 BST 搜索
public boolean searchMatrix(int[][] matrix, int target) {
    int row = 0, col = matrix[0].length - 1;
    while (row < matrix.length && col >= 0) {
        if (matrix[row][col] == target) return true;
        else if (matrix[row][col] > target) col--;  // 太大，左移
        else row++;                                   // 太小，下移
    }
    return false;
}
// 时间 O(m + n)

旋转图像（LeetCode 48）​

先转置，再水平翻转
public void rotate(int[][] matrix) {
    int n = matrix.length;
    // 1. 沿主对角线转置
    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;
        }
    }
    // 2. 每行左右翻转
    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;
        }
    }
}

矩阵置零（LeetCode 73）​

用第一行第一列作标记，O(1) 空间
public void setZeroes(int[][] matrix) {
    int m = matrix.length, n = matrix[0].length;
    boolean firstRowZero = false, firstColZero = false;
    
    // 检查第一行第一列是否有 0
    for (int j = 0; j < n; j++) if (matrix[0][j] == 0) firstRowZero = true;
    for (int i = 0; i < m; i++) if (matrix[i][0] == 0) firstColZero = 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 (firstRowZero) for (int j = 0; j < n; j++) matrix[0][j] = 0;
    if (firstColZero) for (int i = 0; i < m; i++) matrix[i][0] = 0;
}

常见面试问题​

Q1: 矩阵题目的常见技巧？​

答案：

技巧典型题
边界收缩螺旋矩阵
右上角搜索搜索二维矩阵
转置 + 翻转旋转图像
标记法矩阵置零
DFS/BFS岛屿数量

Q2: 如何用 O(1)O(1) 空间对矩阵做操作？​

答案：

利用矩阵自身空间作为标记（如第一行第一列），避免额外开辟数组。

相关链接​