Вопросы Теги

Как повернуть матрицу на 90 градусов без использования дополнительного пространства? [дублировать]

45
задан Community 23 May 2017 в 12:09
поделиться

6 ответов

let a быть индексированием на основе массива nxn 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

Edit Если вы хотите избежать использования temp, это работает (он также вращается в правильном направлении ) на этот раз на питоне. 

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]

Примечание: это работает только для матриц целых чисел.

54
ответ дан 26 November 2019 в 20:48
поделиться

Алгоритм состоит в том, чтобы вращать каждое «кольцо», работая от самого внешнего к самому внутреннему. 

AAAAA
ABBBA
ABCBA
ABBBA
AAAAA

Алгоритм будет сначала вращать все буквы А, затем буквы Б, затем С. Для вращения кольца необходимо переместить сразу 4 значения.

Индекс i находится в диапазоне от 0 до ширины кольца-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.

[Другой ответ появился вместе с кодом, поэтому я не буду повторять это.]

11
ответ дан 26 November 2019 в 20:48
поделиться

Я наткнулся на следующую реализацию:

Для квадратных матриц: 

for n = 0 to N - 2
    for m = n + 1 to N - 1
        swap A(n,m) with A(m,n)

Для прямоугольных матриц: 

for each length>1 cycle C of the permutation
    pick a starting address s in C
    let D = data at s
    let x = predecessor of s in the cycle
    while x ≠ s
        move data from x to successor of x
        let x = predecessor of x
    move data from D to successor of s

Дополнительную информацию можно найти здесь: http: // en.wikipedia.org/wiki/In-place_matrix_transposition

0
ответ дан 26 November 2019 в 20:48
поделиться

См. эту статью для преобразования матрицы на месте; также Google для "транспонирования матрицы на месте". Его легко приспособить для поворота на 90 градусов. Чтобы транспонировать квадратные матрицы, вы просто меняете b [i] [j] на b [j] [i] , где b [k] [l] - a [n * k + l] . На неквадратных матрицах это значительно сложнее. «Без лишнего места» - довольно сильное требование, может быть, вы имели в виду O (1) пространство? (при условии, что целые числа имеют фиксированный размер) Реализация на C ++: здесь .

3
ответ дан 26 November 2019 в 20:48
поделиться

Вам нужна одна временная переменная, тогда она просто позволяет перемещать элементы. 

temp = A[0];
A[0] = A[6];
A[6] = A[8];
A[8] = A[2];
A[2] = temp;
temp = A[1];
A[1] = A[3];
A[3] = A[7];
A[7] = A[5];
A[5] = temp;
1
ответ дан 26 November 2019 в 20:48
поделиться

Транспонируйте и меняйте местами строки или столбцы (в зависимости от того, хотите ли вы повернуть влево или вправо).

e. г. 

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

Все эти операции можно выполнять без выделения памяти.

104
ответ дан 26 November 2019 в 20:48
поделиться