Как вы поворачиваете двухмерный массив?

Здесь он находится в C #

 int[,] array = new int[4,4] { { 1,2,3,4 }, { 5,6,7,8 }, { 9,0,1,2 }, { 3,4,5,6 } }; int[,] rotated = RotateMatrix(array, 4); static int[,] RotateMatrix(int[,] matrix, int n) { int[,] ret = new int[n, n]; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { ret[i, j] = matrix[n - j - 1, i]; } } return ret; } 

O (n ^ 2) и O (1) пространственный алгоритм (без каких-либо обходных решений и hanky-panky!)

Повернуть на +90:

1. транспонировать
2. Переверните каждую строку

Повернуть на -90:

Способ 1:

1. транспонировать
2. Обратить каждую колонку

Способ 2:

1. Переверните каждую строку
2. транспонировать

Повернуть на +180:

Способ 1. Поворот на +90 дважды.

Способ 2 : Обратить каждую строку и затем перевернуть каждый столбец (Transpose)

Повернуть на -180:

Способ 1 : Повернуть на -90 дважды

Способ 2 : Обратить каждый столбец, а затем развернуть каждую строку

Способ 3 : Повернуть на +180, поскольку они одинаковы

Я хотел бы добавить немного больше деталей. В этом ответе ключевые понятия повторяются, темп медленный и преднамеренно повторяющийся. Приведенное здесь решение не является наиболее синтаксически компактным, однако оно предназначено для тех, кто хочет узнать, что такое rotation матрицы и результирующая реализация.

Во-первых, что такое matrix? Для целей этого ответа matrix представляет собой только сетку, где ширина и высота одинаковы. Обратите внимание: ширина и высота матрицы могут быть разными, но для простоты в этом руководстве рассматриваются только матрицы с одинаковой шириной и высотой ( квадратные матрицы ). И да, матрицы – это множественное число матрицы.

Примеры матриц: 2 × 2, 3 × 3 или 5 × 5. Или, в более общем плане, N × N. Матрица 2 × 2 будет иметь 4 квадрата, потому что 2 × 2 = 4. Матрица 5 × 5 будет иметь 25 квадратов, потому что 5 × 5 = 25. Каждый квадрат называется элементом или элементом. Мы будем представлять каждый элемент с периодом ( . ) На диаграммах ниже:

Матрица 2 × 2

 . . . . 

Матрица 3 × 3

 . . . . . . . . . 

Матрица 4 × 4

 . . . . . . . . . . . . . . . . 

Итак, что значит вращать матрицу? Возьмем матрицу 2 × 2 и поместим некоторые числа в каждый элемент, чтобы можно было наблюдать rotation:

 0 1 2 3 

Вращение этого на 90 gradleусов дает нам:

 2 0 3 1 

Мы буквально повернули всю матрицу один раз вправо, как поворот рулевого колеса автомобиля. Это может помочь подумать о «опрокидывании» матрицы на ее правой стороне. Мы хотим написать функцию в Python, которая принимает матрицу и поворачивается один раз вправо. Подпись функции будет:

 def rotate(matrix): # Algorithm goes here. 

Матрица будет определена с использованием двумерного массива:

 matrix = [ [0,1], [2,3] ] 

Поэтому первая позиция индекса обращается к строке. Вторая позиция индекса обращается к столбцу:

 matrix[row][column] 

Мы будем определять функцию утилиты для печати матрицы.

 def print_matrix(matrix): for row in matrix: print row 

Один из способов вращения матрицы – это сделать слой за раз. Но что такое слой? Подумайте о луке. Подобно слоям лука, когда каждый слой удаляется, мы движемся к центру. Другими аналогами являются кукла Матрёшки или игра с посылкой.

Ширина и высота матрицы определяют количество слоев в этой матрице. Давайте используем разные символы для каждого слоя:

Матрица 2 × 2 имеет 1 слой

 . . . . 

Матрица 3 × 3 имеет 2 слоя

 . . . . x . . . . 

Матрица 4 × 4 имеет 2 слоя

 . . . . . xx . . xx . . . . . 

Матрица 5 × 5 имеет 3 слоя

 . . . . . . xxx . . x O x . . xxx . . . . . . 

Матрица 6 × 6 имеет 3 слоя

 . . . . . . . xxxx . . x OO x . . x OO x . . xxxx . . . . . . . 

Матрица 7 × 7 имеет 4 слоя

 . . . . . . . . xxxxx . . x OOO x . . x O - O x . . x OOO x . . xxxxx . . . . . . . . 

Вы можете заметить, что увеличение ширины и высоты матрицы на единицу, не всегда увеличивает количество слоев. Взяв вышеприведенные матрицы и выполнив табуляцию слоев и размеров, мы увидим, что количество слоев увеличивается один раз на каждые два приращения ширины и высоты:

 +-----+--------+ | N×N | Layers | +-----+--------+ | 1×1 | 1 | | 2×2 | 1 | | 3×3 | 2 | | 4×4 | 2 | | 5×5 | 3 | | 6×6 | 3 | | 7×7 | 4 | +-----+--------+ 

Однако не все слои должны вращаться. Матрица 1 × 1 остается прежней до и после вращения. Центральный слой 1 × 1 всегда остается прежним до и после вращения независимо от того, насколько велика общая matrix:

 +-----+--------+------------------+ | N×N | Layers | Rotatable Layers | +-----+--------+------------------+ | 1×1 | 1 | 0 | | 2×2 | 1 | 1 | | 3×3 | 2 | 1 | | 4×4 | 2 | 2 | | 5×5 | 3 | 2 | | 6×6 | 3 | 3 | | 7×7 | 4 | 3 | +-----+--------+------------------+ 

Учитывая матрицу N × N, как мы можем программно определить количество слоев, которые нам нужно вращать? Если мы разделим ширину или высоту на два и проигнорируем остаток, мы получим следующие результаты.

 +-----+--------+------------------+---------+ | N×N | Layers | Rotatable Layers | N/2 | +-----+--------+------------------+---------+ | 1×1 | 1 | 0 | 1/2 = 0 | | 2×2 | 1 | 1 | 2/2 = 1 | | 3×3 | 2 | 1 | 3/2 = 1 | | 4×4 | 2 | 2 | 4/2 = 2 | | 5×5 | 3 | 2 | 5/2 = 2 | | 6×6 | 3 | 3 | 6/2 = 3 | | 7×7 | 4 | 3 | 7/2 = 3 | +-----+--------+------------------+---------+ 

Обратите внимание, как N/2 соответствует числу слоев, которые необходимо повернуть? Иногда число вращающихся слоев на единицу меньше общего количества слоев в матрице. Это происходит, когда самый внутренний слой сформирован только из одного элемента (т.е. матрицы 1 × 1) и, следовательно, его не нужно поворачивать. Это просто игнорируется.

Нам, несомненно, понадобится эта информация в нашей функции, чтобы повернуть матрицу, поэтому добавим ее сейчас:

 def rotate(matrix): size = len(matrix) # Rotatable layers only. layer_count = size / 2 

Теперь мы знаем, что такое слои и как определить количество слоев, которые на самом деле нужно вращать, как мы изолируем один слой, чтобы мы могли его вращать? Во-первых, мы проверяем матрицу от внешнего слоя, внутрь, до самого внутреннего слоя. Матрица 5 × 5 состоит всего из трех слоев и двух слоев, которые должны вращаться:

 . . . . . . xxx . . x O x . . xxx . . . . . . 

Рассмотрим сначала столбцы. Позиция столбцов, определяющих самый внешний слой, если считать, что мы отсчитываем от 0, равны 0 и 4:

 +--------+-----------+ | Column | 0 1 2 3 4 | +--------+-----------+ | | . . . . . | | | . xxx . | | | . x O x . | | | . xxx . | | | . . . . . | +--------+-----------+ 

0 и 4 также являются позициями строк для самого внешнего слоя.

 +-----+-----------+ | Row | | +-----+-----------+ | 0 | . . . . . | | 1 | . xxx . | | 2 | . x O x . | | 3 | . xxx . | | 4 | . . . . . | +-----+-----------+ 

Это всегда будет иметь место, поскольку ширина и высота одинаковы. Поэтому мы можем определить позиции столбца и строки слоя только с двумя значениями (а не с четырьмя).

Двигаясь вовнутрь ко второму слою, положение столбцов равно 1 и 3. И, да, вы догадались, это одинаково для строк. Важно понимать, что нам приходилось увеличивать и уменьшать позиции строк и столбцов при перемещении внутрь к следующему слою.

 +-----------+---------+---------+---------+ | Layer | Rows | Columns | Rotate? | +-----------+---------+---------+---------+ | Outermost | 0 and 4 | 0 and 4 | Yes | | Inner | 1 and 3 | 1 and 3 | Yes | | Innermost | 2 | 2 | No | +-----------+---------+---------+---------+ 

Итак, чтобы проверить каждый слой, нам нужен цикл с увеличивающимися и убывающими счетчиками, которые представляют перемещение внутрь, начиная с самого внешнего слоя. Мы будем называть это нашей «петлей слоя».

 def rotate(matrix): size = len(matrix) layer_count = size / 2 for layer in range(0, layer_count): first = layer last = size - first - 1 print 'Layer %d: first: %d, last: %d' % (layer, first, last) # 5x5 matrix matrix = [ [ 0, 1, 2, 3, 4], [ 5, 6, 6, 8, 9], [10,11,12,13,14], [15,16,17,18,19], [20,21,22,23,24] ] rotate(matrix) 

Приведенный выше код пересекает позиции (строки и столбца) любых слоев, которые должны вращаться.

 Layer 0: first: 0, last: 4 Layer 1: first: 1, last: 3 

Теперь у нас есть петля, обеспечивающая положение строк и столбцов каждого слоя. Первичные и last переменные определяют позицию индекса для первых и последних строк и столбцов. Возвращаясь к нашим таблицам строк и столбцов:

 +--------+-----------+ | Column | 0 1 2 3 4 | +--------+-----------+ | | . . . . . | | | . xxx . | | | . x O x . | | | . xxx . | | | . . . . . | +--------+-----------+ +-----+-----------+ | Row | | +-----+-----------+ | 0 | . . . . . | | 1 | . xxx . | | 2 | . x O x . | | 3 | . xxx . | | 4 | . . . . . | +-----+-----------+ 

Таким образом, мы можем перемещаться по слоям матрицы. Теперь нам нужен способ навигации внутри слоя, чтобы мы могли перемещать элементы вокруг этого слоя. Обратите внимание: элементы никогда не «перескакивают» с одного слоя на другой, но они перемещаются внутри своих соответствующих слоев.

Вращение каждого элемента в слое вращает весь слой. Вращение всех слоев в матрице вращает всю матрицу. Это предложение очень важно, поэтому, пожалуйста, постарайтесь сделать все возможное, чтобы понять его, прежде чем двигаться дальше.

Теперь нам нужен способ перемещения движущихся элементов, т. Е. Поворот каждого элемента, а затем слоя и, в конечном счете, матрицы. Для простоты мы вернемся к матрице 3×3 – которая имеет один вращающийся слой.

 0 1 2 3 4 5 6 7 8 

Наш цикл слоев содержит индексы первого и последнего столбцов, а также первую и последнюю строки:

 +-----+-------+ | Col | 0 1 2 | +-----+-------+ | | 0 1 2 | | | 3 4 5 | | | 6 7 8 | +-----+-------+ +-----+-------+ | Row | | +-----+-------+ | 0 | 0 1 2 | | 1 | 3 4 5 | | 2 | 6 7 8 | +-----+-------+ 

Поскольку наши матрицы всегда квадратные, нам нужны только две переменные: first и last , так как позиции индексов одинаковы для строк и столбцов.

 def rotate(matrix): size = len(matrix) layer_count = size / 2 # Our layer loop i=0, i=1, i=2 for layer in range(0, layer_count): first = layer last = size - first - 1 # We want to move within a layer here. 

Первичные и последние переменные могут быть легко использованы для ссылки на четыре угла матрицы. Это связано с тем, что сами углы могут быть определены с использованием различных перестановок first и last (без вычитания, сложения или смещения этих переменных):

 +---------------+-------------------+-------------+ | Corner | Position | 3x3 Values | +---------------+-------------------+-------------+ | top left | (first, first) | (0,0) | | top right | (first, last) | (0,2) | | bottom right | (last, last) | (2,2) | | bottom left | (last, first) | (2,0) | +---------------+-------------------+-------------+ 

По этой причине мы начинаем rotation на внешних четырех углах – сначала будем вращать их. Давайте выделим их с помощью * .

 * 1 * 3 4 5 * 7 * 

Мы хотим поменять каждый * на * справа от него. Итак, давайте раскроем наши углы, определяемые с использованием только разных перестановок first и last :

 def rotate(matrix): size = len(matrix) layer_count = size / 2 for layer in range(0, layer_count): first = layer last = size - first - 1 top_left = (first, first) top_right = (first, last) bottom_right = (last, last) bottom_left = (last, first) print 'top_left: %s' % (top_left) print 'top_right: %s' % (top_right) print 'bottom_right: %s' % (bottom_right) print 'bottom_left: %s' % (bottom_left) matrix = [ [0, 1, 2], [3, 4, 5], [6, 7, 8] ] rotate(matrix) 

Выход должен быть:

 top_left: (0, 0) top_right: (0, 2) bottom_right: (2, 2) bottom_left: (2, 0) 

Теперь мы могли бы легко поменять каждый из углов внутри нашей петли слоя:

 def rotate(matrix): size = len(matrix) layer_count = size / 2 for layer in range(0, layer_count): first = layer last = size - first - 1 top_left = matrix[first][first] top_right = matrix[first][last] bottom_right = matrix[last][last] bottom_left = matrix[last][first] # bottom_left -> top_left matrix[first][first] = bottom_left # top_left -> top_right matrix[first][last] = top_left # top_right -> bottom_right matrix[last][last] = top_right # bottom_right -> bottom_left matrix[last][first] = bottom_right print_matrix(matrix) print '---------' rotate(matrix) print_matrix(matrix) 

Матрица перед поворотом углов:

 [0, 1, 2] [3, 4, 5] [6, 7, 8] 

Матрица после поворотных углов:

 [6, 1, 0] [3, 4, 5] [8, 7, 2] 

Большой! Мы успешно повернули каждый угол матрицы. Но мы не вращали элементы в середине каждого слоя. Ясно, что нам нужен способ итерации внутри слоя.

Проблема в том, что единственный цикл в нашей функции до сих пор (наш цикл слоев) переходит на следующий уровень на каждой итерации. Так как наша matrix имеет только один вращающийся слой, петля слоя выходит после вращения только углов. Давайте посмотрим, что происходит с более крупной матрицей 5 × 5 (где два слоя нуждаются в ротации). Код функции опущен, но он остается таким же, как указано выше:

 matrix = [ [0, 1, 2, 3, 4], [5, 6, 7, 8, 9], [10, 11, 12, 13, 14], [15, 16, 17, 18, 19], [20, 21, 22, 23, 24] ] print_matrix(matrix) print '--------------------' rotate(matrix) print_matrix(matrix) 

Выход:

 [20, 1, 2, 3, 0] [ 5, 16, 7, 6, 9] [10, 11, 12, 13, 14] [15, 18, 17, 8, 19] [24, 21, 22, 23, 4] 

Не удивительно, что углы внешнего слоя были повернуты, но вы также можете заметить, что углы следующего слоя (внутрь) также были повернуты. Это имеет смысл. Мы написали код для навигации по слоям, а также для поворота углов каждого слоя. Это похоже на прогресс, но, к сожалению, мы должны сделать шаг назад. Это просто неплохо перемещается на следующий слой, пока предыдущий (внешний) слой не будет полностью повернут. То есть, пока каждый элемент в слое не будет повернут. Вращение только углов не будет!

Сделайте глубокий вдох. Нам нужен еще один цикл. Вложенная петля не меньше. Новый, вложенный цикл будет использовать first и last переменные плюс смещение для перемещения внутри слоя. Мы будем называть этот новый цикл нашим «циклом элемента». Цикл элемента будет посещать каждый элемент вдоль верхней строки, каждый элемент с правой стороны, каждый элемент вдоль нижней строки и каждый элемент вверх с левой стороны.

• Для перемещения вперед по верхней строке требуется, чтобы индекс столбца увеличивался.
• Для перемещения по правой стороне требуется, чтобы индекс строки увеличивался.
• Движение назад по дну требует, чтобы индекс столбца уменьшался.
• Для перемещения по левой стороне требуется, чтобы индекс строки уменьшался.

Это звучит сложнее, но это делается легко, потому что количество раз, которое мы увеличиваем и уменьшаем, чтобы достичь вышеуказанного, остается неизменным по всем четырем сторонам матрицы. Например:

• Переместите 1 элемент по верхней строке.
• Переместите 1 элемент вниз с правой стороны.
• Переместите 1 элемент назад вдоль нижнего ряда.
• Переместите 1 элемент вверх по левой стороне.

Это означает, что мы можем использовать одну переменную в сочетании с first и last переменными для перемещения внутри слоя. Это может помочь заметить, что перемещение по верхней строке и вниз по правой стороне требует увеличения. При движении назад по дну и вверх по левой стороне оба требуют декрементации.

 def rotate(matrix): size = len(matrix) layer_count = size / 2 # Move through layers (ie layer loop). for layer in range(0, layer_count): first = layer last = size - first - 1 # Move within a single layer (ie element loop). for element in range(first, last): offset = element - first # 'element' increments column (across right) top_element = (first, element) # 'element' increments row (move down) right_side = (element, last) # 'last-offset' decrements column (across left) bottom = (last, last-offset) # 'last-offset' decrements row (move up) left_side = (last-offset, first) print 'top: %s' % (top) print 'right_side: %s' % (right_side) print 'bottom: %s' % (bottom) print 'left_side: %s' % (left_side) 

Теперь нам просто нужно назначить верх справа на правую сторону снизу, внизу слева, а левую – вверх. Объединяя все это, мы получаем:

 def rotate(matrix): size = len(matrix) layer_count = size / 2 for layer in range(0, layer_count): first = layer last = size - first - 1 for element in range(first, last): offset = element - first top = matrix[first][element] right_side = matrix[element][last] bottom = matrix[last][last-offset] left_side = matrix[last-offset][first] matrix[first][element] = left_side matrix[element][last] = top matrix[last][last-offset] = right_side matrix[last-offset][first] = bottom 

Учитывая матрицу:

 0, 1, 2 3, 4, 5 6, 7, 8 

Наша функция rotate приводит к:

 6, 3, 0 7, 4, 1 8, 5, 2 

Python:

 rotated = zip(*original[::-1]) # On Python 3, list(zip(*original[::-1])) 

Дешево, я знаю.

И против часовой стрелки:

 rotated_ccw = zip(*original)[::-1] # On Python 3, list(zip(*original))[::-1] 

Как это работает: (Запрошено в комментариях)

zip(*original) будет обменивать оси массива 2d путем укладки соответствующих элементов из списков в новые списки. (Оператор * сообщает функции распределять содержащиеся в списке списки в аргументы)

 >>> zip(*[[1,2,3],[4,5,6],[7,8,9]]) [[1,4,7],[2,5,8],[3,6,9]] 

Оператор [::-1] меняет элементы массива (см. Расширенные fragmentы ).

 >>> [[1,2,3],[4,5,6],[7,8,9]][::-1] [[7,8,9],[4,5,6],[1,2,3]] 

Наконец, объединение этих двух будет приводить к преобразованию вращения.

Изменение размещения [::-1] приведет к изменению списков на разных уровнях матрицы.

Вот тот, который делает поворот на месте вместо использования совершенно нового массива для хранения результата. Я прекратил инициализацию массива и распечатывал его. Это работает только для квадратных массивов, но они могут быть любого размера. Накладные расходы памяти равны размеру одного элемента массива, поэтому вы можете сделать rotation как можно большего массива.

 int a[4][4]; int n = 4; int tmp; for (int i = 0; i < n / 2; i++) { for (int j = i; j < n - i - 1; j++) { tmp = a[i][j]; a[i][j] = a[j][ni-1]; a[j][ni-1] = a[ni-1][nj-1]; a[ni-1][nj-1] = a[nj-1][i]; a[nj-1][i] = tmp; } } 

Здесь есть тонны хорошего кода, но я просто хочу показать, что происходит геометрически, чтобы понять логику кода немного лучше. Вот как я подхожу к этому.

в первую очередь, не путайте это с транспозицией, что очень легко ..

Основная идея состоит в том, чтобы рассматривать его как слои, и мы поворачиваем один слой за раз.

скажем, у нас есть 4×4

 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 

поэтому давайте разложим это, сначала мы поворачиваем 4 угла по существу

 1 4 13 16 

то мы вращаем следующий алмаз, который является своего рода косой

  2 8 9 15 

а затем второй перекошенный алмаз

  3 5 12 14 

так что заботится о внешнем краю, так что по существу мы делаем одну оболочку за раз, пока

наконец, средний квадрат (или если он нечетный только конечный элемент, который не перемещается)

 6 7 10 11 

поэтому теперь давайте выясним индексы каждого слоя, предположим, что мы всегда работаем с самым внешним слоем, мы делаем

 [0,0] -> [0,n-1], [0,n-1] -> [n-1,n-1], [n-1,n-1] -> [n-1,0], and [n-1,0] -> [0,0] [0,1] -> [1,n-1], [1,n-2] -> [n-1,n-2], [n-1,n-2] -> [n-2,0], and [n-2,0] -> [0,1] [0,2] -> [2,n-2], [2,n-2] -> [n-1,n-3], [n-1,n-3] -> [n-3,0], and [n-3,0] -> [0,2] 

так далее и так далее, пока мы не на полпути через край

поэтому в целом картина

 [0,i] -> [i,ni], [i,ni] -> [n-1,n-(i+1)], [n-1,n-(i+1)] -> [n-(i+1),0], and [n-(i+1),0] to [0,i] 

Как я уже сказал в своем предыдущем сообщении, вот какой код на C #, который реализует rotation матрицы O (1) для любой матрицы размера. Для краткости и удобочитаемости нет проверки ошибок или проверки диапазона. Код:

 static void Main (string [] args) { int [,] // create an arbitrary matrix m = {{0, 1}, {2, 3}, {4, 5}}; Matrix // create wrappers for the data m1 = new Matrix (m), m2 = new Matrix (m), m3 = new Matrix (m); // rotate the matricies in various ways - all are O(1) m1.RotateClockwise90 (); m2.Rotate180 (); m3.RotateAnitclockwise90 (); // output the result of transforms System.Diagnostics.Trace.WriteLine (m1.ToString ()); System.Diagnostics.Trace.WriteLine (m2.ToString ()); System.Diagnostics.Trace.WriteLine (m3.ToString ()); } class Matrix { enum Rotation { None, Clockwise90, Clockwise180, Clockwise270 } public Matrix (int [,] matrix) { m_matrix = matrix; m_rotation = Rotation.None; } // the transformation routines public void RotateClockwise90 () { m_rotation = (Rotation) (((int) m_rotation + 1) & 3); } public void Rotate180 () { m_rotation = (Rotation) (((int) m_rotation + 2) & 3); } public void RotateAnitclockwise90 () { m_rotation = (Rotation) (((int) m_rotation + 3) & 3); } // accessor property to make class look like a two dimensional array public int this [int row, int column] { get { int value = 0; switch (m_rotation) { case Rotation.None: value = m_matrix [row, column]; break; case Rotation.Clockwise90: value = m_matrix [m_matrix.GetUpperBound (0) - column, row]; break; case Rotation.Clockwise180: value = m_matrix [m_matrix.GetUpperBound (0) - row, m_matrix.GetUpperBound (1) - column]; break; case Rotation.Clockwise270: value = m_matrix [column, m_matrix.GetUpperBound (1) - row]; break; } return value; } set { switch (m_rotation) { case Rotation.None: m_matrix [row, column] = value; break; case Rotation.Clockwise90: m_matrix [m_matrix.GetUpperBound (0) - column, row] = value; break; case Rotation.Clockwise180: m_matrix [m_matrix.GetUpperBound (0) - row, m_matrix.GetUpperBound (1) - column] = value; break; case Rotation.Clockwise270: m_matrix [column, m_matrix.GetUpperBound (1) - row] = value; break; } } } // creates a string with the matrix values public override string ToString () { int num_rows = 0, num_columns = 0; switch (m_rotation) { case Rotation.None: case Rotation.Clockwise180: num_rows = m_matrix.GetUpperBound (0); num_columns = m_matrix.GetUpperBound (1); break; case Rotation.Clockwise90: case Rotation.Clockwise270: num_rows = m_matrix.GetUpperBound (1); num_columns = m_matrix.GetUpperBound (0); break; } StringBuilder output = new StringBuilder (); output.Append ("{"); for (int row = 0 ; row <= num_rows ; ++row) { if (row != 0) { output.Append (", "); } output.Append ("{"); for (int column = 0 ; column <= num_columns ; ++column) { if (column != 0) { output.Append (", "); } output.Append (this [row, column].ToString ()); } output.Append ("}"); } output.Append ("}"); return output.ToString (); } int [,] // the original matrix m_matrix; Rotation // the current view of the matrix m_rotation; } 

Хорошо, я подниму руку, на самом деле он не будет делать никаких изменений в исходном массиве при вращении. Но в OO-системе это не имеет значения, пока объект выглядит так, как будто он был повернут клиентам classа. На данный момент class Matrix использует ссылки на исходные данные массива, поэтому изменение любого значения m1 также изменит m2 и m3. Небольшое изменение конструктора для создания нового массива и копирования значений в него будет сортироваться.

Хотя поворот данных на месте может быть необходим (возможно, для обновления физически сохраненного представления), он становится более простым и, возможно, более эффективным, чтобы добавить слой косвенности на доступ к массиву, возможно, интерфейс:

 interface IReadableMatrix { int GetValue(int x, int y); } 

Если ваша Matrix уже реализует этот интерфейс, то ее можно повернуть через class декоратора следующим образом:

 class RotatedMatrix : IReadableMatrix { private readonly IReadableMatrix _baseMatrix; public RotatedMatrix(IReadableMatrix baseMatrix) { _baseMatrix = baseMatrix; } int GetValue(int x, int y) { // transpose x and y dimensions return _baseMatrix(y, x); } } 

Вращение + 90 / -90 / 180 gradleусов, переворачивание по горизонтали / вертикали и масштабирование могут быть достигнуты таким же образом.

Производительность должна быть измерена в вашем конкретном сценарии. Однако операция O (n ^ 2) теперь заменена вызовом O (1). Это вызов виртуального метода, который медленнее, чем прямой доступ к массиву, поэтому он зависит от того, как часто вращающийся массив используется после вращения. Если он используется один раз, то этот подход определенно победит. Если он повернут, а затем используется в долгосрочной системе в течение нескольких дней, то rotation на месте может работать лучше. Это также зависит от того, можете ли вы принять авансовую стоимость.

Как и во всех проблемах производительности, измерьте, измерьте, измерьте!

Это лучшая версия этого в Java: я сделал это для матрицы с разной шириной и высотой

• h – высота матрицы после вращения
• w здесь ширина матрицы после вращения

 public int[][] rotateMatrixRight(int[][] matrix) { /* W and H are already swapped */ int w = matrix.length; int h = matrix[0].length; int[][] ret = new int[h][w]; for (int i = 0; i < h; ++i) { for (int j = 0; j < w; ++j) { ret[i][j] = matrix[w - j - 1][i]; } } return ret; } public int[][] rotateMatrixLeft(int[][] matrix) { /* W and H are already swapped */ int w = matrix.length; int h = matrix[0].length; int[][] ret = new int[h][w]; for (int i = 0; i < h; ++i) { for (int j = 0; j < w; ++j) { ret[i][j] = matrix[j][h - i - 1]; } } return ret; } 

Этот код основан на записи Ника Берарди.

Ruby-way: .transpose.map &:reverse

There are a lot of answers already, and I found two claiming O(1) time complexity. The real O(1) algorithm is to leave the array storage untouched, and change how you index its elements. The goal here is that it does not consume additional memory, nor does it require additional time to iterate the data.

Rotations of 90, -90 and 180 degrees are simple transformations which can be performed as long as you know how many rows and columns are in your 2D array; To rotate any vector by 90 degrees, swap the axes and negate the Y axis. For -90 degree, swap the axes and negate the X axis. For 180 degrees, negate both axes without swapping.

Further transformations are possible, such as mirroring horizontally and/or vertically by negating the axes independently.

This can be done through eg an accessor method. The examples below are JavaScript functions, but the concepts apply equally to all languages.

  // Get an array element in column/row order var getArray2d = function(a, x, y) { return a[y][x]; }; //demo var arr = [ [5, 4, 6], [1, 7, 9], [-2, 11, 0], [8, 21, -3], [3, -1, 2] ]; var newarr = []; arr[0].forEach(() => newarr.push(new Array(arr.length))); for (var i = 0; i < newarr.length; i++) { for (var j = 0; j < newarr[0].length; j++) { newarr[i][j] = getArray2d(arr, i, j); } } console.log(newarr); 

A couple of people have already put up examples which involve making a new array.

A few other things to consider:

(a) Instead of actually moving the data, simply traverse the “rotated” array differently.

(b) Doing the rotation in-place can be a little trickier. You’ll need a bit of scratch place (probably roughly equal to one row or column in size). There’s an ancient ACM paper about doing in-place transposes ( http://doi.acm.org/10.1145/355719.355729 ), but their example code is nasty goto-laden FORTRAN.

Addendum:

http://doi.acm.org/10.1145/355611.355612 is another, supposedly superior, in-place transpose algorithm.

Nick’s answer would work for an NxM array too with only a small modification (as opposed to an NxN).

 string[,] orig = new string[n, m]; string[,] rot = new string[m, n]; ... for ( int i=0; i < n; i++ ) for ( int j=0; j < m; j++ ) rot[j, n - i - 1] = orig[i, j]; 

One way to think about this is that you have moved the center of the axis (0,0) from the top left corner to the top right corner. You're simply transposing from one to the other.

Here’s my Ruby version (note the values aren’t displayed the same, but it still rotates as described).

 def rotate(matrix) result = [] 4.times { |x| result[x] = [] 4.times { |y| result[x][y] = matrix[y][3 - x] } } result end matrix = [] matrix[0] = [1,2,3,4] matrix[1] = [5,6,7,8] matrix[2] = [9,0,1,2] matrix[3] = [3,4,5,6] def print_matrix(matrix) 4.times { |y| 4.times { |x| print "#{matrix[x][y]} " } puts "" } end print_matrix(matrix) puts "" print_matrix(rotate(matrix)) 

Выход:

 1 5 9 3 2 6 0 4 3 7 1 5 4 8 2 6 4 3 2 1 8 7 6 5 2 1 0 9 6 5 4 3 

Time – O(N), Space – O(1)

 public void rotate(int[][] matrix) { int n = matrix.length; for (int i = 0; i < n / 2; i++) { int last = n - 1 - i; for (int j = i; j < last; j++) { int top = matrix[i][j]; matrix[i][j] = matrix[last - j][i]; matrix[last - j][i] = matrix[last][last - j]; matrix[last][last - j] = matrix[j][last]; matrix[j][last] = top; } } } 

here’s a in-space rotate method, by java, only for square. for non-square 2d array, you will have to create new array anyway.

 private void rotateInSpace(int[][] arr) { int z = arr.length; for (int i = 0; i < z / 2; i++) { for (int j = 0; j < (z / 2 + z % 2); j++) { int x = i, y = j; int temp = arr[x][y]; for (int k = 0; k < 4; k++) { int temptemp = arr[y][z - x - 1]; arr[y][z - x - 1] = temp; temp = temptemp; int tempX = y; y = z - x - 1; x = tempX; } } } } 

code to rotate any size 2d array by creating new array:

 private int[][] rotate(int[][] arr) { int width = arr[0].length; int depth = arr.length; int[][] re = new int[width][depth]; for (int i = 0; i < depth; i++) { for (int j = 0; j < width; j++) { re[j][depth - i - 1] = arr[i][j]; } } return re; } 

Implementation of dimple’s +90 pseudocode (eg transpose then reverse each row) in JavaScript:

 function rotate90(a){ // transpose from http://www.codesuck.com/2012/02/transpose-javascript-array-in-one-line.html a = Object.keys(a[0]).map(function (c) { return a.map(function (r) { return r[c]; }); }); // row reverse for (i in a){ a[i] = a[i].reverse(); } return a; } 

You can do this in 3 easy steps :

1 )Suppose we have a matrix

  1 2 3 4 5 6 7 8 9 

2 )Take the transpose of the matrix

  1 4 7 2 5 8 3 6 9 

3 )Interchange rows to get rotated matrix

  3 6 9 2 5 8 1 4 7 

Java source code for this:

 public class MyClass { public static void main(String args[]) { Demo obj = new Demo(); /*initial matrix to rotate*/ int[][] matrix = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } }; int[][] transpose = new int[3][3]; // matrix to store transpose obj.display(matrix); // initial matrix obj.rotate(matrix, transpose); // call rotate method System.out.println(); obj.display(transpose); // display the rotated matix } } class Demo { public void rotate(int[][] mat, int[][] tran) { /* First take the transpose of the matrix */ for (int i = 0; i < mat.length; i++) { for (int j = 0; j < mat.length; j++) { tran[i][j] = mat[j][i]; } } /* * Interchange the rows of the transpose matrix to get rotated * matrix */ for (int i = 0, j = tran.length - 1; i != j; i++, j--) { for (int k = 0; k < tran.length; k++) { swap(i, k, j, k, tran); } } } public void swap(int a, int b, int c, int d, int[][] arr) { int temp = arr[a][b]; arr[a][b] = arr[c][d]; arr[c][d] = temp; } /* Method to display the matrix */ public void display(int[][] arr) { for (int i = 0; i < arr.length; i++) { for (int j = 0; j < arr.length; j++) { System.out.print(arr[i][j] + " "); } System.out.println(); } } } 

Вывод:

 1 2 3 4 5 6 7 8 9 3 6 9 2 5 8 1 4 7 

PHP:

 0) { $b[count($a[0])-1][] = array_shift($a[0]); if (count($a[0])==0) { array_shift($a); } } ?> 

This is my implementation, in C, O(1) memory complexity, in place rotation, 90 degrees clockwise:

 #include  #define M_SIZE 5 static void initMatrix(); static void printMatrix(); static void rotateMatrix(); static int m[M_SIZE][M_SIZE]; int main(void){ initMatrix(); printMatrix(); rotateMatrix(); printMatrix(); return 0; } static void initMatrix(){ int i, j; for(i = 0; i < M_SIZE; i++){ for(j = 0; j < M_SIZE; j++){ m[i][j] = M_SIZE*i + j + 1; } } } static void printMatrix(){ int i, j; printf("Matrix\n"); for(i = 0; i < M_SIZE; i++){ for(j = 0; j < M_SIZE; j++){ printf("%02d ", m[i][j]); } printf("\n"); } printf("\n"); } static void rotateMatrix(){ int r, c; for(r = 0; r < M_SIZE/2; r++){ for(c = r; c < M_SIZE - r - 1; c++){ int tmp = m[r][c]; m[r][c] = m[M_SIZE - c - 1][r]; m[M_SIZE - c - 1][r] = m[M_SIZE - r - 1][M_SIZE - c - 1]; m[M_SIZE - r - 1][M_SIZE - c - 1] = m[c][M_SIZE - r - 1]; m[c][M_SIZE - r - 1] = tmp; } } } 

Here is the Java version:

 public static void rightRotate(int[][] matrix, int n) { for (int layer = 0; layer < n / 2; layer++) { int first = layer; int last = n - 1 - first; for (int i = first; i < last; i++) { int offset = i - first; int temp = matrix[first][i]; matrix[first][i] = matrix[last-offset][first]; matrix[last-offset][first] = matrix[last][last-offset]; matrix[last][last-offset] = matrix[i][last]; matrix[i][last] = temp; } } } 

the method first rotate the mostouter layer, then move to the inner layer squentially.

From a linear point of view, consider the matrices:

  1 2 3 0 0 1 A = 4 5 6 B = 0 1 0 7 8 9 1 0 0 

Now take A transpose

  1 4 7 A' = 2 5 8 3 6 9 

And consider the action of A’ on B, or B on A’.
Respectively:

  7 4 1 3 6 9 A'B = 8 5 2 BA' = 2 5 8 9 6 3 1 4 7 

This is expandable for any nxn matrix. And applying this concept quickly in code:

 void swapInSpace(int** mat, int r1, int c1, int r2, int c2) { mat[r1][c1] ^= mat[r2][c2]; mat[r2][c2] ^= mat[r1][c1]; mat[r1][c1] ^= mat[r2][c2]; } void transpose(int** mat, int size) { for (int i = 0; i < size; i++) { for (int j = (i + 1); j < size; j++) { swapInSpace(mat, i, j, j, i); } } } void rotate(int** mat, int size) { //Get transpose transpose(mat, size); //Swap columns for (int i = 0; i < size / 2; i++) { for (int j = 0; j < size; j++) { swapInSpace(mat, i, j, size - (i + 1), j); } } } 

C# code to rotate [n,m] 2D arrays 90 deg right

 using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace MatrixProject { // mattrix class class Matrix{ private int rows; private int cols; private int[,] matrix; public Matrix(int n){ this.rows = n; this.cols = n; this.matrix = new int[this.rows,this.cols]; } public Matrix(int n,int m){ this.rows = n; this.cols = m; this.matrix = new int[this.rows,this.cols]; } public void Show() { for (var i = 0; i < this.rows; i++) { for (var j = 0; j < this.cols; j++) { Console.Write("{0,3}", this.matrix[i, j]); } Console.WriteLine(); } } public void ReadElements() { for (var i = 0; i < this.rows; i++) for (var j = 0; j < this.cols; j++) { Console.Write("element[{0},{1}]=",i,j); this.matrix[i, j] = Convert.ToInt32(Console.ReadLine()); } } // rotate [n,m] 2D array by 90 deg right public void Rotate90DegRight() { // create a mirror of current matrix int[,] mirror = this.matrix; // create a new matrix this.matrix = new int[this.cols, this.rows]; for (int i = 0; i < this.rows; i++) { for (int j = 0; j < this.cols; j++) { this.matrix[j, this.rows - i - 1] = mirror[i, j]; } } // replace cols count with rows count int tmp = this.rows; this.rows = this.cols; this.cols = tmp; } } class Program { static void Main(string[] args) { Matrix myMatrix = new Matrix(3,4); Console.WriteLine("Enter matrix elements:"); myMatrix.ReadElements(); Console.WriteLine("Matrix elements are:"); myMatrix.Show(); myMatrix.Rotate90DegRight(); Console.WriteLine("Matrix rotated at 90 deg are:"); myMatrix.Show(); Console.ReadLine(); } } } 

Результат:

  Enter matrix elements: element[0,0]=1 element[0,1]=2 element[0,2]=3 element[0,3]=4 element[1,0]=5 element[1,1]=6 element[1,2]=7 element[1,3]=8 element[2,0]=9 element[2,1]=10 element[2,2]=11 element[2,3]=12 Matrix elements are: 1 2 3 4 5 6 7 8 9 10 11 12 Matrix rotated at 90 deg are: 9 5 1 10 6 2 11 7 3 12 8 4 

For i:= 0 to X do For j := 0 to X do graphic[j][i] := graphic2[Xi][j]

X is the size of the array the graphic is in.

#transpose is a standard method of Ruby’s Array class, thus:

 % irb irb(main):001:0> m = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 0, 1, 2], [3, 4, 5, 6]] => [[1, 2, 3, 4], [5, 6, 7, 8], [9, 0, 1, 2], [3, 4, 5, 6]] irb(main):002:0> m.reverse.transpose => [[3, 9, 5, 1], [4, 0, 6, 2], [5, 1, 7, 3], [6, 2, 8, 4]] 

The implementation is an n^2 transposition function written in C. You can see it here: http://www.ruby-doc.org/core-1.9.3/Array.html#method-i-transpose by choosing “click to toggle source” beside “transpose”.

I recall better than O(n^2) solutions, but only for specially constructed matrices (such as sparse matrices)

C code for matrix rotation 90 degree clockwise IN PLACE for any M*N matrix

 void rotateInPlace(int * arr[size][size], int row, int column){ int i, j; int temp = row>column?row:column; int flipTill = row < column ? row : column; for(i=0;icolumn?i:0; i