题目:给定一个N*N的矩阵matrix,求把这个矩阵调整成顺时针转动90度后的形式。
例如:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
顺时针转动90度后为:
13 9 5 1
14 10 6 2
15 11 7 3
16 12 8 4
要求:额外空间复杂度为O(1)
解答:
这里任然使用分圈处理的方式,在矩阵中用左上角的坐标(tr,tc)和右下角的坐标(dr,dc)就可以表示一个子矩阵。题目中的矩阵,当(tr,tc)=(0,0)、(dr,dc)=(3,3)时,表示的子矩阵就是整个矩阵,这个子矩阵最外层的部分如下:
1 2 3 4
5 8
9 12
13 14 15 16
在这个外圈中,1,4,16,13为一组,然后1占据4的位置,4占据16的位置,16占据13的位置,13占据1的位置,一组就调完了。然后2,8,15,9为一组,继续调整的过程,最后3,12,14,5为一组,继续占据调整过程。然后(tr,tc)=(0,0)、(dr,dc)=(3,3)的子矩阵外层调整完毕。接下来令tr和tc加1,(tr,tc)=(1,1),令dr,dc减1,即(dr,dc)=(2,2),此时表示的子矩阵如下.
6 7
10 11
这个外层只有一组,占据调整之后就可以了。所以如果子矩阵的大小是M*M,一共就有M-1组,分别进行调整即可。
具体过程请参看如下代码的rotate方法:
1 public void rotate(int[][] matrix)
2
3 {
4
5 int tr=0;
6
7 int tc=0;
8
9 int dr=matrix.length-1;
10
11 int dc=matrix[0].length-1;
12
13 while(tr<dr)
14
15 rotateEdge(matrix,tr++,tc++,dr--,dc--);
16
17 }
18
19
20
21 public void rotateEdge(int[][] m,int tr,int tc,int dr,int dc)
22
23 {
24
25 int times=dc-tc;
26
27 int tmp=0;
28
29 for(int i=0;i!=times;i++)
30
31 {
32
33 tmp=m[tr][tc+i];
34
35 m[tr][tc+i]=m[dr-i][tc];
36
37 m[dr-i][tc]=m[dr][dc-i];
38
39 m[dr][dc-i]=m[tr+i][dc];
40
41 m[tr+i][dc]=tmp;
42
43 }
44
45 }
46
47
View Code
原文链接: https://www.cnblogs.com/guanling222/p/5770443.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/238727
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!