Вдохновленный постом Рэймонда Чена , скажем, у вас есть двумерный массив 4x4, напишите функцию, которая поворачивает его на 90 градусов. Раймонд связывается с решением в псевдокоде, но я хотел бы увидеть некоторые реальные вещи.
[1][2][3][4]
[5][6][7][8]
[9][0][1][2]
[3][4][5][6]
становится:
[3][9][5][1]
[4][0][6][2]
[5][1][7][3]
[6][2][8][4]
Обновление : ответ Ника самый простой, но есть ли способ сделать это лучше, чем n ^ 2? Что, если матрица была 10000x10000?
Ответы:
Вот это в C #
источник
ret[i][j] = matrix[j][n - i - 1]
O (n ^ 2) время и O (1) пространственный алгоритм (без каких-либо обходных путей и чепухи!)
Повернуть на +90:
Повернуть на -90:
Способ 1:
Способ 2:
Повернуть на +180:
Метод 1 : Поворот на +90 дважды
Метод 2 : Переверните каждую строку и затем переверните каждый столбец (Транспонировать)
Повернуть на -180:
Метод 1 : Поворот на -90 дважды
Способ 2 : обратный каждый столбец, а затем обратный каждой строки
Способ 3 : поверните на +180, поскольку они одинаковы
источник
rotateCW = map reverse . transpose
иrotateCCW = transpose . map reverse
Я хотел бы добавить немного больше деталей. В этом ответе ключевые понятия повторяются, темп медленный и намеренно повторяющийся. Представленное здесь решение не является наиболее синтаксически компактным, однако оно предназначено для тех, кто хочет узнать, что такое поворот матрицы и какова ее реализация.
Во-первых, что такое матрица? Для целей этого ответа матрица - это просто сетка, в которой ширина и высота одинаковы. Обратите внимание, что ширина и высота матрицы могут быть разными, но для простоты в этом руководстве рассматриваются только матрицы с одинаковой шириной и высотой ( квадратные матрицы ). И да, матрицы - это множественное число от матрицы.
Примеры матриц: 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 и поместим несколько чисел в каждый элемент, чтобы можно было наблюдать вращение:
Поворот на 90 градусов дает нам:
Мы буквально повернули всю матрицу один раз вправо, как поворот руля автомобиля. Это может помочь подумать о «опрокидывании» матрицы с правой стороны. Мы хотим написать функцию на Python, которая принимает матрицу и поворачивается один раз вправо. Подпись функции будет:
Матрица будет определена с использованием двумерного массива:
Поэтому первая позиция указателя обращается к строке. Вторая позиция указателя обращается к столбцу:
Мы определим функцию полезности для печати матрицы.
Один из способов поворота матрицы состоит в том, чтобы сделать ее слоем за раз. Но что такое слой? Подумай о луке. Также как слои лука, так как каждый слой удаляется, мы движемся к центру. Другие аналогии - кукла Матрешка или игра в парцеллу.
Ширина и высота матрицы определяют количество слоев в этой матрице. Давайте использовать разные символы для каждого слоя:
Матрица 2 × 2 имеет 1 слой
Матрица 3 × 3 имеет 2 слоя
Матрица 4 × 4 имеет 2 слоя
Матрица 5 × 5 имеет 3 слоя
Матрица 6 × 6 имеет 3 слоя
Матрица 7 × 7 имеет 4 слоя
Вы можете заметить, что увеличение ширины и высоты матрицы на единицу не всегда увеличивает количество слоев. Взяв вышеприведенные матрицы и табулируя слои и размеры, мы видим, что количество слоев увеличивается один раз на каждые два приращения ширины и высоты:
Однако не все слои нуждаются во вращении. Матрица 1 × 1 одинакова до и после вращения. Центральный слой 1 × 1 всегда одинаков до и после вращения, независимо от размера всей матрицы:
Учитывая N × N матрицу, как мы можем программно определить количество слоев, которые нам нужно повернуть? Если мы разделим ширину или высоту на два и проигнорируем остаток, мы получим следующие результаты.
Заметьте, как
N/2
совпадает количество слоев, которые нужно повернуть? Иногда количество вращающихся слоев на единицу меньше общего количества слоев в матрице. Это происходит, когда самый внутренний слой сформирован только из одного элемента (то есть матрицы 1 × 1) и, следовательно, не нуждается во вращении. Это просто игнорируется.Нам, несомненно, понадобится эта информация в нашей функции для вращения матрицы, поэтому давайте добавим ее сейчас:
Теперь мы знаем, что такое слои и как определить количество слоев, которые действительно нужно вращать, как мы изолируем один слой, чтобы мы могли вращать его? Во-первых, мы проверяем матрицу от самого внешнего слоя внутрь до самого внутреннего слоя. Матрица 5 × 5 имеет всего три слоя и два слоя, которые нужно вращать:
Давайте сначала посмотрим на столбцы. Положение столбцов, определяющих самый внешний слой, при условии, что мы считаем от 0, равно 0 и 4:
0 и 4 также являются позициями строк для самого внешнего слоя.
Это всегда будет так, поскольку ширина и высота одинаковы. Поэтому мы можем определить позиции столбца и строки слоя только с двумя значениями (а не с четырьмя).
Перемещаясь внутрь ко второму слою, позиции столбцов равны 1 и 3. И, да, как вы уже догадались, это одинаково для строк. Важно понимать, что мы должны увеличивать и уменьшать позиции строк и столбцов при переходе внутрь к следующему слою.
Итак, для проверки каждого слоя нам нужен цикл с увеличивающимися и уменьшающимися счетчиками, которые представляют движение внутрь, начиная с самого внешнего слоя. Мы будем называть это нашей «петлей слоя».
Приведенный выше код перебирает позиции (строки и столбцы) любых слоев, которые нужно вращать.
Теперь у нас есть цикл, предоставляющий позиции строк и столбцов каждого слоя. Переменные
first
иlast
идентифицируют позицию индекса первой и последней строк и столбцов. Возвращаясь к нашим таблицам строк и столбцов:Таким образом, мы можем перемещаться по слоям матрицы. Теперь нам нужен способ навигации внутри слоя, чтобы мы могли перемещать элементы вокруг этого слоя. Обратите внимание, что элементы никогда не «перепрыгивают» с одного слоя на другой, но они перемещаются внутри своих соответствующих слоев.
Вращение каждого элемента в слое вращает весь слой. Вращение всех слоев в матрице вращает всю матрицу. Это предложение очень важно, поэтому, пожалуйста, постарайтесь понять его, прежде чем двигаться дальше.
Теперь нам нужен способ реально перемещать элементы, то есть вращать каждый элемент, а затем слой и, в конечном итоге, матрицу. Для простоты мы вернемся к матрице 3х3, которая имеет один вращающийся слой.
Наш цикл слоя предоставляет индексы первого и последнего столбцов, а также первой и последней строк:
Поскольку наши матрицы всегда квадратные, нам нужны только две переменные,
first
иlast
, поскольку позиции индекса одинаковы для строк и столбцов.Переменные first и last могут быть легко использованы для ссылки на четыре угла матрицы. Это потому, что сами углы могут быть определены с использованием различных перестановок
first
иlast
(без вычитания, сложения или смещения этих переменных):По этой причине мы начинаем вращение с четырех внешних углов - сначала мы их вращаем. Давайте выделим их
*
.Мы хотим поменять каждый
*
с*
справа от него. Итак, давайте распечатаем наши углы, определенные только с использованием различных комбинацийfirst
иlast
:Вывод должен быть:
Теперь мы можем довольно легко поменять каждый из углов внутри нашего цикла слоя:
Матрица перед поворотом углов:
Матрица после поворота углов:
Большой! Мы успешно повернули каждый угол матрицы. Но мы не вращали элементы в середине каждого слоя. Очевидно, нам нужен способ итерации внутри слоя.
Проблема в том, что пока единственная петля в нашей функции (петля слоя) перемещается на следующий слой на каждой итерации. Поскольку наша матрица имеет только один вращающийся слой, петля слоя выходит после поворота только углов. Давайте посмотрим, что происходит с большой матрицей 5 × 5 (где два слоя нужно вращать). Код функции был опущен, но он остается таким же, как указано выше:
Выход:
Не должно быть сюрпризом, что углы внешнего слоя были повернуты, но вы также можете заметить, что углы следующего слоя (внутрь) также были повернуты. Это имеет смысл. Мы написали код для навигации по слоям, а также для поворота углов каждого слоя. Это похоже на прогресс, но, к сожалению, мы должны сделать шаг назад. Это просто бесполезно переходить на следующий слой, пока предыдущий (внешний) слой не будет полностью повернут. То есть, пока каждый элемент в слое не будет повернут. Вращать только углы не получится!
Сделай глубокий вдох. Нам нужен еще один цикл. Вложенная петля не меньше. Новый, вложенный цикл, будет использовать
first
иlast
переменные, плюс смещение , чтобы перемещаться в пределах слоя. Мы назовем этот новый цикл нашим «элементом цикла». Цикл элементов будет посещать каждый элемент в верхней строке, каждый элемент в правой части, каждый элемент в нижней строке и каждый элемент в левой части.Это звучит сложно, но это легко сделать, потому что количество раз, которое мы увеличиваем и уменьшаем для достижения вышеуказанного, остается одинаковым по всем четырем сторонам матрицы. Например:
Это означает , что мы можем использовать одну переменную в сочетании с
first
иlast
переменных для перемещения в пределах слоя. Это может помочь заметить, что перемещение по верхнему ряду и вниз по правой стороне требует увеличения. При движении назад вдоль нижней и левой стороны оба требуют уменьшения.Теперь нам просто нужно назначить верхнюю часть правой стороне, правую сторону нижней части, нижнюю часть левой стороне и левую сторону верхней части. Собрав все это вместе, мы получим:
Учитывая матрицу:
Наша
rotate
функция приводит к:источник
list(zip(*reversed(your_list_of_lists)))
Python:
и против часовой стрелки:
Как это работает:
zip(*original)
поменяет оси двумерных массивов, сложив соответствующие элементы из списков в новые списки. (*
Оператор указывает функции распределять содержащиеся списки в аргументы)[::-1]
Оператор меняет элементы массива (см. Раздел « Расширенные фрагменты» или этот вопрос ):Наконец, объединение двух приведет к преобразованию вращения.
Изменения в расположении
[::-1]
перевернут списки на разных уровнях матрицы.источник
zip(*reversed(original))
вместо того,zip(*original[::-1])
чтобы избежать создания дополнительной копии исходного списка.Вот тот, который делает вращение на месте, вместо того, чтобы использовать совершенно новый массив для хранения результата. Я прекратил инициализацию массива и распечатал его. Это работает только для квадратных массивов, но они могут быть любого размера. Накладные расходы памяти равны размеру одного элемента массива, поэтому вы можете вращать массив настолько, насколько вам нужно.
источник
Здесь много хорошего кода, но я просто хочу показать, что происходит геометрически, чтобы вы могли немного лучше понять логику кода. Вот как я бы подошел к этому.
во-первых, не путайте это с транспозицией, которая очень проста ..
Основная идея состоит в том, чтобы рассматривать его как слои, и мы вращаем один слой за раз.
скажем, у нас есть 4x4
после того, как мы повернем его по часовой стрелке на 90, мы получим
так что давайте разложим это, сначала мы вращаем 4 угла по существу
затем мы вращаем следующий алмаз, который является своего рода искривленным
а затем 2-й скошенный бриллиант
так что заботится о внешнем крае так по существу, мы делаем это по одной оболочке за раз, пока
наконец, средний квадрат (или, если он нечетный, только последний элемент, который не двигается)
так что теперь давайте выясним индексы каждого слоя, предположим, что мы всегда работаем с самым внешним слоем, мы делаем
так и так далее, пока мы не на полпути через край
так в целом картина
источник
Как я уже говорил в моем предыдущем посте, вот некоторый код на C #, который реализует поворот матрицы O (1) для матрицы любого размера. Для краткости и читабельности нет проверки ошибок или диапазона. Код:
Хорошо, я подниму руку, на самом деле при повороте он не вносит никаких изменений в исходный массив. Но в ОО-системе это не имеет значения, если объект выглядит так, как будто он был повернут для клиентов класса. На данный момент класс Matrix использует ссылки на исходные данные массива, поэтому изменение любого значения m1 также изменит m2 и m3. Небольшое изменение в конструкторе для создания нового массива и копирования значений в него позволит разобраться в этом.
источник
Хотя вращение данных на месте может быть необходимым (возможно, для обновления физически сохраненного представления), становится проще и, возможно, более производительным добавить слой косвенности к доступу к массиву, возможно, к интерфейсу:
Если вы
Matrix
уже реализуете этот интерфейс, то его можно повернуть через класс декоратора, например так:Поворот на + 90 / -90 / 180 градусов, переворачивание по горизонтали / вертикали и масштабирование - все это также может быть достигнуто.
Производительность должна быть измерена в вашем конкретном сценарии. Однако операция O (n ^ 2) теперь заменена вызовом O (1). Это виртуальный вызов метода , который является медленнее , чем прямой доступ к массиву, так это зависит от того, как часто поворачивается массив используется после поворота. Если он используется один раз, то этот подход определенно победит. Если его вращать, а затем использовать в долго работающей системе в течение нескольких дней, то вращение на месте может работать лучше. Это также зависит от того, можете ли вы принять предварительную стоимость.
Как и во всех вопросах производительности, измерять, измерять, измерять
источник
Это лучшая версия на Java: я сделал это для матрицы с другой шириной и высотой
Этот код основан на посте Ника Берарди.
источник
Рубин-путь:
.transpose.map &:reverse
источник
array.reverse.transpose
вращать массив по часовой стрелке, аarray.transpose.reverse
вращать против часовой стрелки. Там нет необходимостиmap
.Ответов уже много, и я нашел два, требующих O (1) временной сложности. Реальный O (1) алгоритма оставить хранение массива нетронутым, и изменить , как вы индекс его элементы. Цель в том, что он не потребляет дополнительную память и не требует дополнительного времени для итерации данных.
Повороты на 90, -90 и 180 градусов - это простые преобразования, которые можно выполнять, если вы знаете, сколько строк и столбцов в вашем 2D-массиве; Чтобы повернуть любой вектор на 90 градусов, поменяйте местами оси и отрицайте ось Y. Для -90 градусов поменяйте местами оси и отрицайте ось X. При повороте на 180 градусов обе оси не меняются местами.
Возможны дальнейшие преобразования, такие как зеркальное отражение по горизонтали и / или вертикали путем независимого отрицания осей.
Это можно сделать, например, с помощью метода доступа. Приведенные ниже примеры являются функциями JavaScript, но концепции в равной степени применимы ко всем языкам.
Этот код предполагает наличие массива вложенных массивов, где каждый внутренний массив представляет собой строку.
Метод позволяет читать (или записывать) элементы (даже в случайном порядке), как если бы массив был повернут или преобразован. Теперь просто выберите правильную функцию для вызова, вероятно, по ссылке, и все - и все!
Концепция может быть расширена для применения преобразований аддитивно (и неразрушающе) через методы доступа. В том числе произвольные углы поворота и масштабирования.
источник
Несколько человек уже представили примеры, которые включают создание нового массива.
Несколько других вещей, чтобы рассмотреть:
(a) Вместо того, чтобы фактически перемещать данные, просто пересеките «повернутый» массив по-другому.
(б) Выполнение вращения на месте может быть немного сложнее. Вам понадобится немного места для царапин (вероятно, примерно равного одному размеру строки или столбца). Есть древняя статья ACM о выполнении транспонирования на месте ( http://doi.acm.org/10.1145/355719.355729 ), но их пример кода - отвратительный загруженный FORTRAN.
Приложение:
http://doi.acm.org/10.1145/355611.355612 - еще один, предположительно улучшенный, алгоритм транспонирования на месте.
источник
НикОтвет будет работать и для массива NxM с небольшой модификацией (в отличие от NxN).
Один из способов думать об этом состоит в том, что вы переместили центр оси (0,0) из верхнего левого угла в верхний правый угол. Вы просто переносите из одного в другое.
источник
Время - O (N), Пространство - O (1)
источник
Вот моя версия Ruby (обратите внимание, что значения не отображаются одинаково, но они все еще вращаются, как описано).
Выход:
источник
Вот метод поворота в пространстве, по Java, только для квадрата. для не квадратного 2d массива вам все равно придется создавать новый массив.
код для вращения любого размера 2d массива путем создания нового массива:
источник
Реализация псевдокода +90 для dimple (например, транспонировать, затем перевернуть каждую строку) в JavaScript:
источник
Вы можете сделать это в 3 простых шага :
1 ) Предположим, у нас есть матрица
2 ) Возьмите транспонированную матрицу
3 ) чередуйте строки, чтобы получить повернутую матрицу
Исходный код Java для этого:
Вывод:
источник
Это моя реализация, в C, O (1) сложность памяти, поворот на месте, 90 градусов по часовой стрелке:
источник
Вот версия Java:
метод сначала вращает самый верхний слой, затем последовательно перемещается к внутреннему слою.
источник
С линейной точки зрения рассмотрим матрицы:
Теперь возьми транспонирование
И рассмотрим действие A на B или B на A.
Соответственно:
Это расширяется для любой матрицы nxn. И быстро применить эту концепцию в коде:
источник
C # код для поворота [n, m] 2D массивов на 90 градусов вправо
Результат:
источник
PHP:
Начиная с PHP5.6, транспонирование массива может быть выполнено со слабым
array_map()
вызова. Другими словами, столбцы преобразуются в строки.Код: ( Демо )
$ Транспонировать:
источник
For i:= 0 to X do For j := 0 to X do graphic[j][i] := graphic2[X-i][j]
X - размер массива, в котором находится графика.
источник
#transpose является стандартным методом класса Array в Ruby, таким образом:
Реализация представляет собой функцию транспонирования n ^ 2, написанную на C. Вы можете увидеть ее здесь: http://www.ruby-doc.org/core-1.9.3/Array.html#method-i-transpose , выбрав «click» переключить источник "рядом с" транспонировать ".
Я помню лучше, чем O (n ^ 2) решения, но только для специально построенных матриц (таких как разреженные матрицы)
источник
C-код для поворота матрицы на 90 градусов по часовой стрелке НА МЕСТЕ для любой матрицы M * N
источник
вот моя реализация на месте в C
источник
Вот моя попытка поворота матрицы на 90 градусов, которая является двухшаговым решением в C. Сначала переставьте матрицу на месте, а затем поменяйте местами столбцы.
источник
@dagorym: Ой человек. Я держался за это как хорошую головоломку «мне скучно, что я могу обдумать». Я придумал свой код транспонирования на месте, но попал сюда, чтобы найти ваш, в значительной степени идентичный моему ... ах, хорошо. Вот это в Ruby.
источник
Простой метод C ++, хотя в большом массиве будет большой объем памяти.
источник