如何旋转矩阵90度，而无需使用任何额外的空间？ [英] How to rotate a matrix 90 degrees without using any extra space?

问题描述

  

可能重复：
  <一href="http://stackoverflow.com/questions/2968397/algorithm-to-rotate-an-image-90-degrees-in-place-no-extra-memory">Algorithm旋转图像90度的地方？ （没有额外的内存）

通过说90度，我的意思是说，如果：

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

再经过90度旋转A变成：

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

解决方案

让 A 是一个n阶矩阵0基索引

  F =地板（N / 2）
C = CEIL（N / 2）

对于x = 0到f  -  1
  为Y = 0至C  -  1
    TEMP = A [X，Y]
    一[X，Y] =一个[Y，N-1-X]
    一个[Y，N-1-X] = A [n-1个-X，N-1-y]的
    一个[N-1-X，N-1-Y] = A [n-1个-Y，X]
    一个[N-1-Y，X] =气温
 

修改如果您想避免使用临时，这个工作（这也沿正确的方向），这次在蟒蛇。

 高清ROT2（一）：
  N = LEN（一）
  C =（N + 1）/ 2
  F = N / 2
  x的范围（℃）：
    y的范围内（F）：
      一[X] [Y] =一[X] [Y] ^一个[N-1-y]的[X]
      一个[N-1-y]的[X] =一[X] [Y] ^一个[N-1-y]的[X]
      一[X] [Y] =一[X] [Y] ^一个[N-1-y]的[X]

      一个[N-1-y]的[X] = A [n-1个-Y] [X] ^一个[N-1-X] [n-1个-y]的
      一个[N-1-X] [正 -  1-Y] = A [n-1个-Y] [X] ^一个[N-1-X] [n-1个-y]的
      一个[N-1-y]的[X] = A [n-1个-Y] [X] ^一个[N-1-X] [n-1个-y]的

      一个[N-1-X] [正 -  1-Y] = A [n-1个-X] [n-1个-γ] ^一个[Y] [n-1个-X]
      一个[Y] [n-1个-X] = A [n-1个-X] [n-1个-γ] ^一个[Y] [n-1个-X]
      一个[N-1-X] [正 -  1-Y] = A [n-1个-X] [n-1个-γ] ^一个[Y] [n-1个-X]
 

请注意：这只适用于整数矩阵

Possible Duplicate:
Algorithm to rotate an image 90 degrees in place? (No extra memory)

By saying 90 degrees i mean to say if:

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

then after 90 degree rotation A becomes:

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

解决方案

let a be an nxn array 0 based indexing

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

Edit If you want to avoid using temp, this works (it also rotates in the correct direction) this time in 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]

Note: This only works for matrices of integers.

这篇关于如何旋转矩阵90度，而无需使用任何额外的空间？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！