¹⁵

算法学习笔记4 旋转矩阵（二维数组）（解法有参考）

鱼友9113

2023-09-30 22:51

阅读2509

鱼友9113

2023-09-30 22:51

阅读 2509

https://leetcode.cn/leetbook/read/array-and-string/clpgd/ （篇幅有限，引用一下leetcode~）

这个题我打算记录两种解法：

第一种方法我把它称之为魔方旋转

以二维数组int[][] cube=[1,2,3,4][5,6,7,8][9,10,11,12][13,14,15,16]为例（外层的旋转，就想象成四阶魔方的边框旋转），

魔方旋转一次，对应内外层元素都需要旋，一个一个拆分成大概是这样的过程:

最外层元素：以前的[0,0]元素1，占用原来的[0,3]位置，原来的[0,3]元素4，占用[3,3]位置，原来的[3,3]元素15，占用[3,0]位置，原来的[3，0]元素13，占用[0，0]位置（如图示）

因此元素变化为：

(0,0)->(0,3)

(0,3)->(3,3)

(3,3)->(3,0)

(3,0)->(0,0)

再向内一层：以[0,1]元素2为参照点

因此元素变化为：

(0,1)->(1,3)

(1,3)->(3,2)

(3,2)->(2,0)

(2,0)->(0,1)

再向内一层：以[0,2]元素3为参照点

因此元素变化为：

(0,2)->(2,3)

(2,3)->(3,1)

(3,1)->(1,0)

(1,0)->(0,1)

因此，我们发现了一些规律：

1)当left指针值<=right指针值的时候（可以选用while循环来控制），代表外层的元素遍历完毕，其中，当left指针值=right指针值的时候,代表是奇数矩阵，存在中间元素，不需要反转。（可以联想3*3或者5*5魔方）

2）一共旋转了left(最左索引值) - right轮

因此:

1. 我们先确定指针 left，right，top, bottom指定的index的值：

int left = 0;

// 数组的最大索引值

int right = cube.length - 1;

int top = 0;

int bottom = cube.length - 1;

2. 其次，定义三个临时变量值：

tmp1来存储右上角元素（如以一个图示，tmp1=4,因为已经被第一个元素1踢出去了）,

tmp2为右下角(第一轮的tmp2 = 16),

tmp3为左上角元素(第一轮的tmp2 = 13) 根据三轮的变化，我们发现：

轮数起始位置 tmp1的位置和值 tmp2的位置和值 tmp3的位置和值

1 (0,0) 4(0,3) 16(3,3) 13(3,0)

2 (0,1) 8(1,3) 15(3,2) 9(2,0)

3 (0,2) 12(2,3) 14(3,1) 5(1,0)

于是乎，可以确定他们三个变量在每轮循环的时候所对应的坐标值：

// 右上角

tmp1 = cube[top+i][right]

// 右下角

tmp2 = cube[bottom][right-i]

// 左下角

tmp3 = cube[bottom-i][left]

3.确定好3个tmp的位置后，接下来完成旋转：

1）将tmp1存储左上角的元素

tmp1 = cube[top+i][right];

2）将左上角的值赋值到右上角

cube[top+i][right] = cube[top][left+i]；

3）将tmp2存储右下角的元素

tmp2 = cube[bottom][right-i];

4）再把tmp1赋值给右下角

cube[bottom][right-i] = tmp1;

5）将tmp3存储左下角的元素

tmp3 = cube[bottom-i][left];

6）再把tmp2赋值给左下角

cube[bottom-i][left] = tmp2;

7）将tmp3赋值给左上角

cube[top][left+i] = tmp3;

内层元素的翻转是在外层元素全部翻转完之后，直接一体转：

(1,1)->(1,2)

(1,2)->(2,2)

(2,2)->(2,1)

(2,1)->(1,1)

这个时候，需要left++，right--，top++，bottom--。

因此题解1的代码为：

public void cube(int[][] cube) {

int n = cube.length;

int left = 0;

// 数组的最大索引值

int right = n - 1;

int top = 0;

int bottom = n - 1;

while (right > left){

// 移动外层元素

for (int i = 0; i < right - left; i++) {

// 将左上角的数据存储在tmp1中

int tmp1 = cube[top+i][right];

// 移动：将左上角的元素赋值给右上角

cube[top+i][right] = cube[top][left+i];

// 将右下角的值存储在tmp2中

int tmp2 = cube[bottom][right-i];

// 移动：将tmp1赋值给右下角

cube[bottom][right-i] = tmp1;

// 将tmp3存储左下角的元素

int tmp3 = cube[bottom-i][left];

// 移动：再把tmp2赋值给左下角

cube[bottom-i][left] = tmp2;

// 将tmp3赋值给左上角

cube[top][left+i] = tmp3;

}

// 移动内层的元素

left++;

right--;

top++;

bottom--;

}

此解法参考：https://www.bilibili.com/video/BV1pk4y1g7oz/?spm_id_from=333.999.0.0&vd_source=ab6bf39fa792415c33eb5ed1159fb95b

第二种是元素对换（采用异或的方式实现元素数值的交换）

以二维数组int[][] mitrix=[[1,2,3][4,5,6][7,8,9]]为例：

初始态是： ---> 目标态是：

1，2，3 7，4，1

4，5，6 8，5，2

7，8，9 9，6，3

然后，总结一下初始态和最终态元素的索引位置：

元素初始态索引(row，col) 最终态索引

1 (0,0) (0,2)

2 (0,1) (1,2)

3 (0,2) (2,2)

4 (1,0) (0,1)

5 (1,1) (1,1)

6 (1,2) (2,1)

7 (2,0) (0,0)

8 (2,1) (1,0)

9 (2,2) (2,0)

由此可见，最终态的row值是原来初始态的col值，最终态的col是mitrix的最大长度-初始态的row值，即为mitrix.length-1-row，因此可以表示为mitrix[col][mitrix.length-1-row]

1.元素交换：可以采用异或的方式来实现元素之间的对调：

a' = a^b

b' = a'^b

a'' = a'^b'

🤔虽然不太恰当，但为了方便理解我用a'，b'和a''来区分。

来看一下图形的布局：我们可以尝试先以中心列为对称轴对折交换元素，然后再以右对角线进行元素交换，然后再上下元素交换。

所以我们相当于是首先操作矩阵的四角的元素，分别是

[0,0] [0,mitrix.length-1] [mitrix.length-1,0] [mitrix.length-1,mitrix.length-1]

1）左右对折交换元素：是红色框与橙色框进行对调，因此按照元素对调公式，代码是：

// 也就是[0,0]元素1和[0,2]元素3进行对调

matrix[0][0] = matrix[0][0]^matrix[0][matrix.length-1]

matrix[0][matrix.length-1] = matrix[0][0]^matrix[0][matrix.length-1];

matrix[0][0] = matrix[0][0]^matrix[0][matrix.length-1];

于是乎，原来1的位置是3，原来3的位置变成了1。因此矩阵变成：

3，2，1

4，5，6

7，8，9

2）接下来进行右对角线对折交换元素：在1）完成后，由现在的[0,0]位置元素和[2,2]元素进行对调，也就是3将要和9进行位置对调。

和1）同理，因此代码是

// 也就是1)之后，现在的[0,0]元素3和[2,2]元素9进行对调

matrix[0][0] = matrix[0][0]^matrix[matrix.length-1][matrix.length-1];

matrix[matrix.length-1][matrix.length-1-0] = matrix[0][0]^matrix[matrix.length-1][matrix.length-1];

matrix[0][0] = matrix[0][0]^matrix[matrix.length-1][matrix.length-1];

于是乎，2）中的3的位置是9，9的位置变成了3。因此矩阵变成：

9，2，1

4，5，6

7，8，3

3)最后再进行上下元素的对调：在2）完成后，由现在的[0,0]位置元素和[0,2]元素进行对调，也就是9将要和7进行对调。

同理，因此代码是

// 也就是2)之后，现在的[0,0]元素9和[2,0]元素7进行对调

matrix[0][0] = matrix[0][0]^matrix[matrix.length-1-0][0];

matrix[matrix.length-1-0][0] = matrix[0][0]^matrix[matrix.length-1][0];

matrix[0][0] = matrix[0][0]^matrix[matrix.length-1-0][0];

于是乎，3）中9的位置是7，7的位置变成了9。因此矩阵变成：

7，2，1

4，5，6

9，8，3

2.考虑到这个过程是逐个操作元素的，我们采用双层for循环：

1）外层循环用来控制旋转的层数，也就是从外向内一层一层地旋转矩阵。由于在旋转过程中，每一层的边界元素都会被交换到正确的位置，所以只需要旋转矩阵的上半部分即可。因此，边界条件是数组长度的一半，即 i < matrix.length/2（这点我现在还是很懵，姑且就先理解成一个萝卜一个坑的换座位吧，如果之后有更好的理解会补充。）

2）内层for循环控制每一层中需要进行元素交换的范围，换句话说就是是每一层的边界元素或者从外向内逐层遍历需要进行交换的元素。

3）然后，每次完成一圈元素对调后，需每次将外层的索引位置 -1，从而来确定下一轮的索引位置。

因此题解2的代码为：

public void rotate(int[][] matrix) {

for (int i = 0; i < matrix.length; i++) {

for (int j = i; j < matrix.length - (i + 1); j++) {

// 左右对折交换一次

matrix[i][j] = matrix[i][j]^matrix[j][matrix.length-1-i];

matrix[j][matrix.length-1-i] = matrix[i][j]^matrix[j][matrix.length-1-i];

matrix[i][j] = matrix[i][j]^matrix[j][matrix.length-1-i];

// 右对角线交换一次（逆时针是左对角线交换）

matrix[i][j] = matrix[i][j]^matrix[matrix.length-1-i][matrix.length-1-j];