如何在不使用任何额外空间的情况下将矩阵旋转90度？

Question

可能重复:
将图像旋转90度的算法？(没有额外的记忆)

说90度我的意思是说:

A = {1,2,3,
     4,5,6,
     7,8,9}

然后在90度旋转后A成为:

A = {7,4,1,
     8,5,2,
     9,6,3}

Answer 1

转置和交换行或列(取决于您是要向左还是向右旋转).

例如

1) original matrix

1 2 3
4 5 6
7 8 9

2) transpose

1 4 7
2 5 8
3 6 9

3-a) change rows to rotate left

3 6 9
2 5 8
1 4 7

3-b) or change columns to rotate right

7 4 1
8 5 2
9 6 3

所有这些操作都可以在不分配内存的情况下完成.

Answer 2

让a是n×n的阵列基于0的索引

f = floor(n/2)
c = ceil(n/2)

for x = 0 to f - 1
  for y = 0 to c - 1
    temp = a[x,y]
    a[x,y] = a[y,n-1-x]
    a[y,n-1-x] = a[n-1-x,n-1-y]
    a[n-1-x,n-1-y] = a[n-1-y,x]
    a[n-1-y,x] = temp

编辑如果你想避免使用temp,这次可以在python中运行(它也以正确的方向旋转).

def rot2(a):
  n = len(a)
  c = (n+1) / 2
  f = n / 2
  for x in range(c):
    for y in range(f):
      a[x][y] = a[x][y] ^ a[n-1-y][x]
      a[n-1-y][x] = a[x][y] ^ a[n-1-y][x]
      a[x][y] = a[x][y] ^ a[n-1-y][x]

      a[n-1-y][x] = a[n-1-y][x] ^ a[n-1-x][n-1-y]
      a[n-1-x][n-1-y] = a[n-1-y][x] ^ a[n-1-x][n-1-y]
      a[n-1-y][x] = a[n-1-y][x] ^ a[n-1-x][n-1-y]

      a[n-1-x][n-1-y] = a[n-1-x][n-1-y]^a[y][n-1-x]
      a[y][n-1-x] = a[n-1-x][n-1-y]^a[y][n-1-x]
      a[n-1-x][n-1-y] = a[n-1-x][n-1-y]^a[y][n-1-x]

注意:这仅适用于整数矩阵.

Answer 3

该算法是旋转每个"环",从最外面到最里面工作.

AAAAA
ABBBA
ABCBA
ABBBA
AAAAA

该算法将首先旋转所有A,然后是B,然后是C.旋转环需要一次移动4个值.

索引i的范围为0..ring-width-1,例如对于A,宽度为5.

  (i,0) -> temp
  (0, N-i-1) -> (i, 0)
  (N-i-1, N-1) -> (0, N-i-1)
  (N-1, i) -> (N-i-1, N-1)
  temp -> (N-1, i)  

然后对每个连续的内环重复这一过程,使坐标偏移,使环宽减小2.

[代码中出现了另一个答案,所以我不会重复.]