图解翻转矩阵问题

matrix

0.如何将一张图翻转90度

给定一张图片，如何将它旋转 90 度？ 可以将图视为可以存储在缓冲区中的二维矩阵。 提供了矩阵维度和它的地址。 怎么转呢？

• 下面的是个例子

* * * ^ * * *
* * * | * * *
* * * | * * *   
* * * | * * *

顺时针翻转90度后，变成：

* * * *
* * * *
* * * *
-- - - >
* * * *
* * * *
* * * *

想法很简单，将源矩阵的每一行转换为最终图的所需列，将使用辅助缓冲区来转换图。 从上图我们可以观察到

源图的第一行 -> 目标图的最后一列
源图的第二行 -> 目标图的倒数第二列
...
源图的最后一行 -> 目标图的第一列

如图：可以将m✖️n的矩阵转化为n✖️m矩阵，逻辑如下：

private void rotate(int m, int n, int[][] source, int[][] dest) {
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            dest[c][m - 1 - r] = source[r][c];
        }
    }
}

代码

static class _1st {


    public static void main(String[] args) {
        _1st handler = new _1st();
        int[][] source = {{1, 2, 3, 4},
                {5, 6, 7, 8},
                {9, 10, 11, 12}};
        int m = source.length, n = source[0].length;
        handler.display(source, m, n);
        int[][] dest = new int[n][m];
        handler.rotate(m, n, source, dest);
        handler.display(dest, n, m);
    }


    /**
     * @param m      source的 row
     * @param n      source的 col
     * @param source 源矩阵
     * @param dest   目标矩阵
     */
    private void rotate(int m, int n, int[][] source, int[][] dest) {
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                dest[c][m - 1 - r] = source[r][c];
            }
        }
    }


    private void display(int[][] matrix, int R, int C) {
        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) {
                System.out.printf("%d\t", matrix[r][c]);
            }
            System.out.print("\n");
        }
    }

}

输出

1	 2	3  	4	
5	 6	7 	8	
9	10	11	12	
-------------------  
9	  5	 1	
10	6  2	
11	7	 3	
12	8	 4

1.如何原地将矩阵旋转90度

比如说需要将下面的矩阵逆时针旋转90度

case 1:
Matrix:
 1  2  3
 4  5  6
 7  8  9
Output:
 3  6  9 
 2  5  8 
 1  4  7 
case 2:
Input:
 1  2  3  4 
 5  6  7  8 
 9 10 11 12 
13 14 15 16 
Output:
 4  8 12 16 
 3  7 11 15 
 2  6 10 14 
 1  5  9 13

在第一部分已经讨论过，如果利用多余的空间翻转矩阵了，本部分讨论下如何原地空间复杂度的方式翻转矩阵

思路

要在没有多余空间的情况下解决问题，将数组旋转为正方形，将矩阵划分为正方形或环。

例如，一个 4✖️4 的矩阵将有 2 个环。

• 第一个环由它的第一行、最后一列、最后一行和第一列组成。

• 第二个环由第二行、倒数第二列、倒数第二行和第二列组成。

这个想法是对于每个方形循环，以逆时针方向交换与矩阵中相应单元格相关的元素，即从上到左、从左到下、从下到右和从右到上一次，只使用一个临时变量来实现这一点。

图解结果如下：

算法

• 1.在N边的矩阵中有N/2个正方形或环。一次处理一个正方形，运行一个环，一次遍历矩阵一个环，即从 0 循环到 N/2 – 1，循环计数器为 i。

• 2.考虑当前正方形中的 4 个元素组，一次旋转 4 个元素。 因此，一个循环中此类组的数量为N – 2*i。

• 3.所以在从 x 到 N - x - 1 的每个循环中运行一个环，循环计数器为 y。

• 4.当前组中的元素是 (x, y), (y, N-1-x), (N-1-x, N-1-y), (N-1-y, x)，现在旋转这4个元素，即(x, y) <- (y, N-1-x), (y, N-1-x)<- (N-1-x, N-1-y), (N- 1-x, N-1-y)<- (N-1-y, x), (N-1-y, x)<- (x, y)

代码

static class _2nd {
    public static void main(String[] args) {
        _2nd handler = new _2nd();
        int[][] matrix = {
                {1, 2, 3, 4},
                {5, 6, 7, 8},
                {9, 10, 11, 12},
                {13, 14, 15, 16}
        };
        int N = matrix.length;
        handler.display(matrix, N);
        handler.rotateMatrix(matrix, N);
        handler.display(matrix, N);
    }


    private void rotateMatrix(int[][] matrix, int N) {
        //考虑每一个环
        for (int x = 0; x < N / 2; x++) {
            for (int y = x; y < N - x - 1; y++) {
                int t = matrix[x][y];
                matrix[x][y] = matrix[y][N - 1 - x];
                matrix[y][N - 1 - x] = matrix[N - 1 - x][N - 1 - y];
                matrix[N - 1 - x][N - 1 - y] = matrix[N - 1 - y][x];
                matrix[N - 1 - y][x] = t;
            }
        }
    }


    private void display(int[][] matrix, int N) {
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                System.out.printf("%d\t", matrix[r][c]);
            }
            System.out.print("\n");
        }
    }
}f

输出

1	 2	3	 4	
5	 6	7	 8	
9	 10	11 12	
13 14	15 16	
-------------
4	8	12 16	
3	7	11 15	
2	6	10 14	
1	5	9	 13	

复杂度分析

• 时间复杂度：O(n*n) 其中n是矩阵的长度

• 空间复杂度: O(1)，没有使用到额外的空间，只是一个变量

不过还有另外一种思路：

• 1.翻转每一行

• 2.执行转置

2.再论如何原地将矩阵旋转90度

上面已经讨论了如何进行原地的矩阵翻转了，下面再给出另外一种思路

主要的思路是：将矩阵的转置，然后反转转置矩阵的列。

算法

• 1.为了解决给定的问题，有两个任务。 第一个是找到转置，第二个是在不使用额外空间的情况下反转列。

• 2.矩阵的转置是当矩阵翻转其对角线时，即元素的行索引变为列索引，反之亦然。 因此，要找到转置，将位置 (i, j) 处的元素与 (j, i) 互换。执行两个循环，外循环从 0 到行数，内循环从 0 到外循环的索引。

• 3.要反转转置矩阵的列，请运行两个嵌套循环，外循环从 0 到列数，内循环从 0 到行数/2，将 (i, j) 处的元素与 (i, row[count-1 -j])对调，其中 i 和 j 分别是内循环和外循环的索引。

代码

static class _3rd {
    public static void main(String[] args) {
        _3rd handler = new _3rd();
        int[][] matrix = {{1, 2, 3, 4},
                {5, 6, 7, 8},
                {9, 10, 11, 12},
                {13, 14, 15, 16}};
        handler.display(matrix);
        handler.rotate(matrix);
        handler.display(matrix);
    }


    private void rotate(int[][] matrix) {
        transpose(matrix);
        reverseColumns(matrix);
    }


    //按矩阵的的列翻转
    private void reverseColumns(int[][] matrix) {
        for (int i = 0; i < matrix[0].length; i++) {
            for (int j = 0, k = matrix[0].length - 1; j < k; j++, k--) {
                int t = matrix[j][i];//[j,i] <-> [k,i]
                matrix[j][i] = matrix[k][i];
                matrix[k][i] = t;
            }
        }
    }


    //转置
    private void transpose(int[][] matrix) {
        for (int r = 0; r < matrix.length; r++) {
            for (int c = r; c < matrix[0].length; c++) {
                int t = matrix[c][r];
                matrix[c][r] = matrix[r][c];
                matrix[r][c] = t;
            }
        }
    }


    private void display(int[][] matrix) {
        for (int r = 0; r < matrix.length; r++) {
            for (int c = 0; c < matrix[0].length; c++) {
                System.out.printf("%d\t", matrix[r][c]);
            }
            System.out.print("\n");
        }
    }
}

输出

1	2	3	4	
5	6	7	8	
9	10	11	12	
13	14	15	16	
-----------------
4	8	12	16	
3	7	11	15	
2	6	10	14	
1	5	9	13

复杂度分析

• 时间复杂度：O(R*C) 其中R和C是矩阵的行列

• 空间复杂度: O(1)，没有使用到额外的空间

3.如何原地将矩阵旋转180度

上面的两部分解决了如何旋转90度的问题，那么180度怎么处理？

例子:

Input :  1  2  3
         4  5  6
         7  8  9
Output : 9 8 7 
         6 5 4 
         3 2 1

Input :  1 2 3 4 
         5 6 7 8 
         9 0 1 2 
         3 4 5 6 
Output : 6 5 4 3 
         2 1 0 9 
         8 7 6 5 
         4 3 2 1

方法1（仅打印旋转矩阵）

• 从上图中，可以简单地将矩阵旋转180度，以相反的方式打印给定的矩阵。

代码

static class _4th {
    public static void main(String[] args) {
        _4th handler = new _4th();
        int[][] matrix = {{1, 2, 3, 4},
                {5, 6, 7, 8},
                {9, 10, 11, 12},
                {13, 14, 15, 16}};
        handler.rotateMatrix(matrix);
    }


    private void rotateMatrix(int[][] matrix) {
        int N = matrix.length;
        for (int i = N - 1; i >= 0; i--) {
            for (int j = N - 1; j >= 0; j--) {
                System.out.printf("%d ", matrix[i][j]);
            }
            System.out.println();
        }
    }
}

输出

16 15 14 13 
12 11 10 9 
8 7 6 5 
4 3 2 1 

复杂度分析

• 时间复杂度：O(N*N) 其中N是矩阵的行列

• 空间复杂度: O(1)，没有使用到额外的空间

方法2：原地翻转(转置翻转列两次)

算法

• 1.查找矩阵的转置。

• 2.反转转置的列。

• 3.找到矩阵的转置。

• 4.转置的反转列

static class _5th {
    public static void main(String[] args) {
        _5th handler = new _5th();
        int[][] matrix = {{1, 2, 3, 4},
                {5, 6, 7, 8},
                {9, 10, 11, 12},
                {13, 14, 15, 16}};
        handler.display(matrix);
        handler.rotate(matrix);
        handler.display(matrix);
    }


    private void rotate(int[][] matrix) {
        transpose(matrix);
        reverseColumns(matrix);
        transpose(matrix);
        reverseColumns(matrix);
    }


    //按矩阵的的列翻转
    private void reverseColumns(int[][] matrix) {
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0, k = matrix[0].length - 1; j < k; j++, k--) {
                int t = matrix[j][i];//[j,i] <-> [k,i]
                matrix[j][i] = matrix[k][i];
                matrix[k][i] = t;
            }
        }
    }


    //转置
    private void transpose(int[][] matrix) {
        for (int r = 0; r < matrix.length; r++) {
            for (int c = r; c < matrix[0].length; c++) {
                int t = matrix[c][r];
                matrix[c][r] = matrix[r][c];
                matrix[r][c] = t;
            }
        }
    }


    private void display(int[][] matrix) {
        for (int r = 0; r < matrix.length; r++) {
            for (int c = 0; c < matrix[0].length; c++) {
                System.out.printf("%d\t", matrix[r][c]);
            }
            System.out.print("\n");
        }
    }
}

输出

1	2	3	4	
5	6	7	8	
9	10	11	12	
13	14	15	16	
-----------------
16	15	14	13	
12	11	10	9	
8	7	6	5	
4	3	2	1	

复杂度分析

• 时间复杂度：O(R*C) 其中R和C是矩阵的行列

• 空间复杂度: O(1)，没有使用到额外的空间

方法3：位置交换

上面的方式其实是将矩阵翻转90度做了两次，其实有更好的方法

static class _6th {
    public static void main(String[] args) {
        _6th handler = new _6th();
        int[][] matrix = {{1, 2, 3, 4},
                {5, 6, 7, 8},
                {9, 10, 11, 12},
                {13, 14, 15, 16}};
        handler.display(matrix);
        handler.rotateMatrix(matrix);
        handler.display(matrix);
        matrix = new int[][]{
                {1, 2, 3, 4, 5},
                {6, 7, 8, 9, 10},
                {11, 12, 13, 14, 15},
                {16, 17, 18, 19, 20},
                {21, 22, 23, 24, 25}
        };
        handler.display(matrix);
        handler.rotateMatrix(matrix);
        handler.display(matrix);

    }

    private void display(int[][] matrix) {
        for (int r = 0; r < matrix.length; r++) {
            for (int c = 0; c < matrix[0].length; c++) {
                System.out.printf("%d\t", matrix[r][c]);
            }
            System.out.print("\n");
        }
    }

    private void reverseRow(int[][] matrix, int r) {
        int C = matrix[r].length;
        for (int c = 0; c < C / 2; c++) {
            int t = matrix[r][c];
            matrix[r][c] = matrix[r][C - c - 1];
            matrix[r][C - c - 1] = t;
        }
    }

    private void rotateMatrix(int[][] matrix) {
        int R = matrix.length, C = matrix[0].length;
        if (R % 2 != 0) {
            reverseRow(matrix, R / 2);
        }
        for (int r = 0; r <= R / 2 - 1; r++) {
            for (int c = 0; c < C; c++) {
                int t = matrix[r][c];
                matrix[r][c] = matrix[R - r - 1][C - c - 1];
                matrix[R - r - 1][C - c - 1] = t;
            }
        }
    }
}

输出

1	2	3	4	
5	6	7	8	
9	10	11	12	
13	14	15	16	
-----------------
16	15	14	13	
12	11	10	9	
8	7	6	5	
4	3	2	1	
-----------------
1	2	3	4	5	
6	7	8	9	10	
11	12	13	14	15	
16	17	18	19	20	
21	22	23	24	25
-----------------	
25	24	23	22	21	
20	19	18	17	16	
15	14	13	12	11	
10	9	8	7	6	
5	4	3	2	1

4.将矩阵的每个环逆时针旋转 K 个元素

给定一个 M*N 阶矩阵和一个值 K，将矩阵的每个环逆时针旋转 K 个元素。 如果任何环中的元素小于等于 K，则不要旋转它。

Input : k = 3
        mat[4][4] = {{1, 2, 3, 4},
                    {5, 6, 7, 8},
                    {9, 10, 11, 12},
                    {13, 14, 15, 16}}
Output: 4 8  12 16
        3 10  6 15
        2 11  7 14
        1  5  9 13

Input : k = 2
        mat[3][4] = {{1, 2, 3, 4},
                    {10, 11, 12, 5},
                    {9, 8, 7, 6}}
Output: 3 4  5  6
        2 11 12 7
        1 10  9 8

思路

想法是以螺旋形式遍历矩阵， 这是解决这个问题的算法：

• 1.创建一个大小为 M*N 的辅助数组 temp[]。

• 2.以螺旋形式开始遍历矩阵并将当前环的元素存储在 temp[] 数组中。 在将元素存储在 temp 中时，跟踪当前环的开始和结束位置。

• 3.对于存储在 temp[] 中的每个环，旋转该子数组 temp[]

• 4.对矩阵的每个环重复此过程。

• 5.在最后一次遍历矩阵中再次螺旋并将 temp[] 数组的元素复制到矩阵。

有了上面的这些铺垫，可以来解决几道题目：

48. 旋转图像

• 题目要求的是原地旋转，顺时针旋转

参考1.如何原地将矩阵旋转90度，挪动下调换的坐标即可

        public void rotate(int[][] matrix) {
            //考虑每一个环
            int R = matrix.length, C = matrix[0].length;
            for (int x = 0; x < R / 2; x++) {
                for (int y = x; y < R - x - 1; y++) {
                    int t = matrix[x][y];
                    matrix[x][y] = matrix[R - 1 - y][x];
                    matrix[R - 1 - y][x] = matrix[R - 1 - x][C - 1 - y];
                    matrix[R - 1 - x][C - 1 - y] = matrix[y][C - 1 - x];
                    matrix[y][C - 1 - x] = t;
                }
            }
        }

也可以参考2.再论如何原地将矩阵旋转90度，在做第二步翻转的时候，将行翻转变成列翻转

public void rotate(int[][] matrix) {
    transpose(matrix);
    reverseColumns(matrix);
}

//按矩阵的的列翻转 翻转的是第一列和最后一列 第二列和倒数第二列 如此...
private void reverseColumns(int[][] matrix) {
    for (int i = 0; i < matrix.length; i++) {
        for (int j = 0, k = matrix.length - 1; j < k; j++, k--) {
            int t = matrix[i][j];//[i,j] <-> [i,k]
            matrix[i][j] = matrix[i][k];
            matrix[i][k] = t;
        }
    }
}


//转置
private void transpose(int[][] matrix) {
    for (int r = 0; r < matrix.length; r++) {
        for (int c = r; c < matrix[0].length; c++) {
            int t = matrix[c][r];
            matrix[c][r] = matrix[r][c];
            matrix[r][c] = t;
        }
    }
}

面试题 01.07. 旋转矩阵

这一题等同于48题

867. 转置矩阵

这一题只需要用到转置的那段代码即可,但是这一题m*n的矩阵，m和n可能不相同，所以用到额外空间，简单模拟即可

    public int[][] transpose(int[][] matrix) {
        int R = matrix.length,C= matrix[0].length;
        int[][] res = new int[C][R];
        for(int i =0;i<R;i++){
            for(int j =0;j<C;j++){
                res[j][i] = matrix[i][j];
            }
        }
        return res;
    }