图解翻转矩阵问题
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 41.如何原地将矩阵旋转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 14.将矩阵的每个环逆时针旋转 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[] 数组的元素复制到矩阵。
有了上面的这些铺垫，可以来解决几道题目：
题目要求的是原地旋转，顺时针旋转
参考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;
}
}
}这一题等同于48题
这一题只需要用到转置的那段代码即可,但是这一题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;
}Last updated