【每日算法Day 41】矩阵1

一些矩阵的访问与控制操作：旋转（转置+翻转）和按圈层访问等。

LeetCode 48. 旋转图像 (opens new window)

题目描述

给定一个 n × n 的二维矩阵表示一个图像。 将图像顺时针旋转 90 度。

说明： 你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。

示例

给定 matrix = 
[
  [1,2,3],
  [4,5,6],
  [7,8,9]
],

原地旋转输入矩阵，使其变为:
[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]

解题思路

首先将矩阵进行转置，再依次反转每一行就能得到结果。时间复杂度为O(n^2)，原地操作空间复杂度为O(1)。

public void rotate(int[][] matrix) {
    if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) return;
    int n = matrix.length;
    //转置
    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;
        }
    }
    //逐行翻转
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n / 2; j++) {
            int temp = matrix[i][j];
            matrix[i][j] = matrix[i][n - j - 1];
            matrix[i][n - j - 1]=temp;
        }
    }
}

LeetCode 54. 螺旋矩阵 (opens new window)

题目描述

给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。

示例

输入:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
输出: [1,2,3,6,9,8,7,4,5]

解题思路

这一题就是顺时针打印矩阵，思路是设置left、right、up、down四个虚拟边界，遇到边界是更改方向并收缩上一个边界,如果上下或者左右的边界冲突则跳出循环。每个元素只访问一次，时间复杂度为O(m*n)，空间复杂度为O(1)。

public List<Integer> spiralOrder(int [][] matrix) {
    ArrayList<Integer> list = new ArrayList<>();
    if (matrix==null||matrix.length==0||matrix[0]==null||matrix[0].length==0) return list;
    int left = 0, right = matrix[0].length - 1, up = 0, down = matrix.length-1;
    while(true){
        for(int col=left;col<=right;col++){
            list.add(matrix[up][col]);
        }
        // 向下逼近
        if (++up > down) break;

        for(int row=up;row<=down;row++){
            list.add(matrix[row][right]);
        }
        // 向左逼近
        if (--right < left) break;

        for(int col=right;col>=left;col--){
            list.add(matrix[down][col]);
        }
        // 向上逼近
        if (--down < up) break;

        for(int row=down;row>=up;row--){
            list.add(matrix[row][left]);
        }
        // 向右逼近
        if (++left > right) break;
    }
    return list;
}

此外还看到了通过变相转置矩阵和使用标记数组的方法，不过一个更费时间一个更费空间。

LeetCode 59. 螺旋矩阵 II (opens new window)

题目描述

给定一个正整数 n，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。

示例

输入: 3
输出:
[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

解题思路

先创建数组再和上一题类似向数组中填充数据即可。每个元素只访问一次，时间复杂度为O(m*n)，空间复杂度为O(1)。

public int[][] generateMatrix(int n) {
    int[][] matrix = new int[n][n];
    int count = 1;
    int left = 0, right = n - 1, up = 0, down = n - 1;
    while (true) {
        for (int col = left; col <= right; col++) {
            matrix[up][col] = count++;
        }
        if (++up > down) break;

        for (int row = up; row <= down; row++) {
            matrix[row][right] = count++;
        }
        if (--right < left) break;

        for (int col = right; col >= left; col--) {
            matrix[down][col] = count++;
        }
        if (--down < up) break;

        for (int row = down; row >= up; row--) {
            matrix[row][left] = count++;
        }
        if (++left > right) break;
    }
    return matrix;
}

其实这一题由于固定是n*n的正方形，并且填充的数count由1~n^2递增，所以可以直接检查count来跳出循环。