Как вы вращаете двумерный массив?

302

Вдохновленный постом Рэймонда Чена , скажем, у вас есть двумерный массив 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?

свилиам
источник
99
Как ты мог обойтись без n ^ 2? Все элементы должны быть прочитаны и установлены, и есть n ^ 2 элементов
erikkallen
1
См. Также stackoverflow.com/questions/848025/rotating-bitmaps-in-code
Марко ван де Воорт
9
Какой твой п? Вы не говорите, является ли двумерный массив квадратным (это не в общем случае! Например, вектор - это матрица с одним измерением 1), но вы, похоже, подразумеваете, что n - это ширина и высота, и, следовательно, имеют n² элементов. , Было бы более разумно, чтобы n было числом элементов с n = w × h.
niXar
1
Вот быстрый способ сделать это: сохранить индексы строк и столбцов (скажем, i и j). Транспонирование занимает постоянное время (просто поменяйте местами индексы :). Вы можете сделать то же самое с вращениями (играть с индексами).
saadtaame
4
В случае, если п ^ 2 не представляется возможным. Вы можете создать интерфейс для доступа к каждому элементу. Затем, учитывая (i, j), примените вращение для (i, j) доступа к повернутому элементу и возврата. Может быть не самый лучший, но работает.
путать

Ответы:

140

Вот это в 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;
}
Ник Берарди
источник
6
Конечно, а как насчет решения с использованием O (1) памяти?
AlexeyMK
20
Ваше решение имеет O (n ^ 2) пространственной сложности. Нужно сделать лучше
Kshitij Jain
6
Как насчет матрицы NXM?
Рохит
18
Сложность линейна по количеству элементов в массиве. Если N - количество элементов, сложность O (N). Если N - длина стороны, тогда да, сложность - O (N ^ 2), но это все еще оптимально. Вы должны прочитать каждый элемент хотя бы один раз. Печать на матрице такая же сложность
Алехандро
6
Для поворота на -90 градусов:ret[i][j] = matrix[j][n - i - 1]
Дункан Лук
387

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

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

  1. Транспонирование
  2. Переверните каждый ряд

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

Способ 1:

  1. Транспонирование
  2. Переверните каждый столбец

Способ 2:

  1. Переверните каждый ряд
  2. Транспонирование

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

Метод 1 : Поворот на +90 дважды

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

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

Метод 1 : Поворот на -90 дважды

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

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

ямочка
источник
4
Это было очень полезно для меня; Я смог написать алгоритм, как только я узнал «[псевдо-] версию кода» этой операции. Спасибо!
Дума
13
Один из моих любимых ТАК ответов всех времен. Очень поучительно!
g33kz0r
2
Вот реализация JavaScript JSFiddle, если кому-то интересно.
г-н Поливирл
6
Поверните на -90: (1) Переверните каждую строку; (2) Транспонировать. Haskell: rotateCW = map reverse . transposeиrotateCCW = transpose . map reverse
Томас Эдинг
5
Какая разница между вращением 180 и -180?
Цянь Чен
178

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

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

Примеры матриц: 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 и поместим несколько чисел в каждый элемент, чтобы можно было наблюдать вращение:

0 1
2 3

Поворот на 90 градусов дает нам:

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 слоя

. . . .
. x x .
. x x .
. . . .

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

. . . . .
. x x x .
. x O x .
. x x x .
. . . . .

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

. . . . . .
. x x x x .
. x O O x .
. x O O x .
. x x x x .
. . . . . .

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

. . . . . . .
. x x x x x .
. x O O O x .
. x O - O x .
. x O O O x .
. x x x x x .
. . . . . . .

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

+-----+--------+
| 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 всегда одинаков до и после вращения, независимо от размера всей матрицы:

+-----+--------+------------------+
| 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 имеет всего три слоя и два слоя, которые нужно вращать:

. . . . .
. x x x .
. x O x .
. x x x .
. . . . .

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

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

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

+-----+-----------+
| Row |           |
+-----+-----------+
|   0 | . . . . . |
|   1 | . x x x . |
|   2 | . x O x . |
|   3 | . x x x . |
|   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

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

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

+-----+-----------+
| Row |           |
+-----+-----------+
|   0 | . . . . . |
|   1 | . x x x . |
|   2 | . x O x . |
|   3 | . x x x . |
|   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 могут быть легко использованы для ссылки на четыре угла матрицы. Это потому, что сами углы могут быть определены с использованием различных перестановок 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)       |
+---------------+-------------------+-------------+

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

* 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]

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

Проблема в том, что пока единственная петля в нашей функции (петля слоя) перемещается на следующий слой на каждой итерации. Поскольку наша матрица имеет только один вращающийся слой, петля слоя выходит после поворота только углов. Давайте посмотрим, что происходит с большой матрицей 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 (i.e. layer loop).
    for layer in range(0, layer_count):

            first = layer
            last = size - first - 1

            # Move within a single layer (i.e. 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  
Джек
источник
Сначала я чувствовал себя «вау, лучшее объяснение когда-либо», но после прочтения этого пару раз (чтобы убедиться, что я не пропустил ничего важного в море слов), мое мнение изменилось на «человек, я понимаю, могу мы продолжаем двигаться, пожалуйста? До сих пор голосовали за то, что потратили часы, чтобы составить такой сложный ответ.
Абхиджит Саркар
1
@AbhijitSarkar - Спасибо за предварительное голосование, и я надеюсь, что оно хотя бы немного помогло. Конечно, вы правы, мой ответ многословен. Это было, однако, намеренно, в отличие от подавляющего большинства ответов. Как я сказал в самом начале своего ответа: «В этом ответе ключевые понятия повторяются, темп медленный и намеренно повторяющийся». Если у вас есть изменения, которые сохраняют ясность и необходимую повторяемость, но уменьшают количество слов, я очень открыт для предложений. Или просто отредактируйте :)
Джек,
@ Джек Действительно хорошее объяснение. Тем не менее, я не мог понять, как вы пришли к смещению = элемент - первый и последний = размер - первый - 1? Трудно понять это? Кроме того, последнее смещение такое же, как смещение?
ashishjmeshram
1
TL; DR:list(zip(*reversed(your_list_of_lists)))
Борис
127

Python:

rotated = list(zip(*original[::-1]))

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

rotated_ccw = list(zip(*original))[::-1]

Как это работает:

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

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

[::-1]Оператор меняет элементы массива (см. Раздел « Расширенные фрагменты» или этот вопрос ):

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

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

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

bcdan
источник
3
Я считаю, что этот код происходит от Питера Норвига: norvig.com/python-iaq.html
Josip
Вы можете использовать zip(*reversed(original))вместо того, zip(*original[::-1])чтобы избежать создания дополнительной копии исходного списка.
Борис
70

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

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][n-i-1];
        a[j][n-i-1]     = a[n-i-1][n-j-1];
        a[n-i-1][n-j-1] = a[n-j-1][i];
        a[n-j-1][i]     = tmp;
    }
}
дагорым
источник
Я вижу по крайней мере одну ошибку. Если вы собираетесь опубликовать код, протестируйте его или, по крайней мере, скажите, что вы еще этого не сделали.
Хью Аллен
1
Куда? Укажите это, и я исправлю это. Я проверил его, и он отлично работал как на нечетных, так и на четных массивах.
Дагорым
2
это прекрасное решение. Ум может совершать такие умения, если настроен на цель. с O (n2) на O (1)
MoveFast
2
Это не O (1); это все еще O (n ^ 2)
дума
11
Это O (n ^ 2) с памятью O (1).
Нил
38

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

во-первых, не путайте это с транспозицией, которая очень проста ..

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

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

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

а затем 2-й скошенный бриллиант

        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,n-i], [i,n-i] -> [n-1,n-(i+1)], [n-1,n-(i+1)] -> [n-(i+1),0], and [n-(i+1),0] to [0,i]
доводка
источник
что значит "на полпути через край"? Я вижу множество алгоритмов, зацикливающихся до N / 2, а другие зацикливаются до N, но я не вижу, откуда исходит N / 2.
ПДН
Я считаю, что это то же решение, что и при взломе интервью по кодированию. Но мне нравится пошаговое объяснение. Очень мило и тщательно.
Нафстор
@PDN Этот ответ объясняет это подробно.
Матиас
35

Как я уже говорил в моем предыдущем посте, вот некоторый код на C #, который реализует поворот матрицы 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;
}

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

Skizz
источник
4
Браво! Это очень хорошее решение, и я не знаю, почему это не принятый ответ.
martinatime
@martinatime: возможно, потому что это в 5 раз больше
жаба
@Toad: Ну, написание кода - это всегда компромисс между конкурирующими требованиями: скорость, размер, стоимость и т. Д.
Skizz 4.10.10
15
правда ... другая проблема заключается в том, что матрица на самом деле не вращается, а вращается «как раз вовремя». Что отлично подходит для доступа к нескольким элементам, но было бы ужасно, если бы эта матрица использовалась в вычислениях или манипуляциях с изображениями. Таким образом, высказывание O (1) не совсем справедливо.
жаба
23

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

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

Если вы Matrixуже реализуете этот интерфейс, то его можно повернуть через класс декоратора, например так:

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 градусов, переворачивание по горизонтали / вертикали и масштабирование - все это также может быть достигнуто.

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

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

Дрю Ноакс
источник
1
+1 ... А если матрица действительно большая и вы получаете доступ только к нескольким элементам (редко), это еще более эффективно
лотерея
16
Кажется немного несправедливым называть это O (1) временным решением. Чтобы решить проблему, поставленную OP, это все еще займет O (n ^ 2) время. Мало того, это не решит проблему, потому что она возвращает транспонирование . В приведенном примере нет транспонирования в качестве решения.
Влад Импала
5
Теперь, если все, что вам нужно, это первые 3 элемента матрицы, это прекрасное решение, но проблема состоит в том, чтобы получить полностью преобразованную матрицу (т.е. при условии, что вам нужны все элементы матрицы). Вызов этого O (1) является методом кредитного дефолтного свопа анализа алгоритмов - вы не решили проблему, вы просто передали ее кому-то другому :)
Ана Беттс
4
@Paul Betts: Я понял вашу точку зрения, но, как я уже писал выше в комментариях, даже если вы на самом деле перенесли матрицу, вам все равно придется писать цикл, если вы хотите считывать значения. Таким образом, чтение всех значений из матрицы всегда равно O (N ^ 2). Разница здесь в том, что если вы транспонируете, поворачиваете, масштабируете, снова масштабируете и т. Д., То вы все равно получаете удар O (N ^ 2) только один раз. Как я уже сказал, это не всегда лучшее решение, но во многих случаях оно уместно и стоит. ОП, казалось, искал волшебное решение, и это так близко, как вы получите.
Дрю Ноакс
9
Мне нравится этот ответ, но я хочу кое-что указать. Распечатка декорированной матрицы (и выполнение других последовательных операций чтения в целом) может быть намного медленнее, чем выполнение такой же операции с матрицей, повернутой в памяти, и это происходит не только из-за вызовов виртуальных методов. Для большой матрицы вы значительно увеличите число пропусков кэша, читая «вниз», а не «поперек».
Майк Дэниелс
18

Это лучшая версия на 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;
}

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

Мартейн Курто
источник
Спасибо. Это был самый ясный код Java здесь. Вопрос - Как вы / Ник придумали часть [w - j - 1]? Глядя на ответ @ tweaking, я вижу, как вы можете получить это с помощью примеров индукции / решения. Просто интересно, вот как это было получено или оно основано на каком-то математическом принципе, относящемся к Матрицам.
Квест Монгер
17

Рубин-путь: .transpose.map &:reverse

Накилон
источник
1
Это даже проще: array.reverse.transposeвращать массив по часовой стрелке, а array.transpose.reverseвращать против часовой стрелки. Там нет необходимости map.
Георгий Гзиришвили
13

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

Повороты на 90, -90 и 180 градусов - это простые преобразования, которые можно выполнять, если вы знаете, сколько строк и столбцов в вашем 2D-массиве; Чтобы повернуть любой вектор на 90 градусов, поменяйте местами оси и отрицайте ось Y. Для -90 градусов поменяйте местами оси и отрицайте ось X. При повороте на 180 градусов обе оси не меняются местами.

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

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

 // 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);

// Get an array element rotated 90 degrees clockwise
function getArray2dCW(a, x, y) {
  var t = x;
  x = y;
  y = a.length - t - 1;
  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[0].length; i++) {
  for (var j = 0; j < newarr.length; j++) {
    newarr[j][i] = getArray2dCW(arr, i, j);
  }
}
console.log(newarr);

// Get an array element rotated 90 degrees counter-clockwise
function getArray2dCCW(a, x, y) {
  var t = x;
  x = a[0].length - y - 1;
  y = t;
  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[0].length; i++) {
  for (var j = 0; j < newarr.length; j++) {
    newarr[j][i] = getArray2dCCW(arr, i, j);
  }
}
console.log(newarr);

// Get an array element rotated 180 degrees
function getArray2d180(a, x, y) {
  x = a[0].length - x - 1;
  y = a.length - y - 1;
  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.forEach(() => newarr.push(new Array(arr[0].length)));

for (var i = 0; i < newarr[0].length; i++) {
  for (var j = 0; j < newarr.length; j++) {
    newarr[j][i] = getArray2d180(arr, i, j);
  }
}
console.log(newarr);

Этот код предполагает наличие массива вложенных массивов, где каждый внутренний массив представляет собой строку.

Метод позволяет читать (или записывать) элементы (даже в случайном порядке), как если бы массив был повернут или преобразован. Теперь просто выберите правильную функцию для вызова, вероятно, по ссылке, и все - и все!

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

Jason Oster
источник
Однако ни один из них не был повернут из исходного массива. Первый, конечный результат просто транспонирован. Второй, вы, кажется, только что перетасовали ряды или отразили по горизонтальному центру. Третий, вы только перевернули строки, а четвертый также транспонирован. Ни один из которых на самом деле не был «повернут».
SM177Y
В последних двух примерах есть ошибки. Тривиально исправить. Я четко указал, что это решение не является ротацией на месте. Это функция преобразования, которая делает ее пригодной для ленивых итераций.
Джейсон Остер
За исключением того, что нет ротации, так что вы на самом деле не ответили на то, что спросил ОП.
SM177Y
@ SM177Y Другой редактор добавил неработающий пример кода в мой ответ. Я вижу, как вы были смущены этим. Я исправил ошибки в циклах итерации. Предоставленные функции фактически «вращают» данные в массивах.
Джейсон Остер
Также важной деталью является то, что пример кода действительно стирает исходный ответ, который я дал, который пытался проиллюстрировать силу функциональных преобразований в решениях линейной сложности пространства-времени. При функциональном преобразовании вы уже выполняете итерацию или иным образом обращаетесь к элементам массива , поэтому преобразование считается «свободным» в смысле постоянной пространственной и временной сложности.
Джейсон Остер
10

Несколько человек уже представили примеры, которые включают создание нового массива.

Несколько других вещей, чтобы рассмотреть:

(a) Вместо того, чтобы фактически перемещать данные, просто пересеките «повернутый» массив по-другому.

(б) Выполнение вращения на месте может быть немного сложнее. Вам понадобится немного места для царапин (вероятно, примерно равного одному размеру строки или столбца). Есть древняя статья ACM о выполнении транспонирования на месте ( http://doi.acm.org/10.1145/355719.355729 ), но их пример кода - отвратительный загруженный FORTRAN.

Приложение:

http://doi.acm.org/10.1145/355611.355612 - еще один, предположительно улучшенный, алгоритм транспонирования на месте.

nsanders
источник
Я согласен с этим. Иметь метод, который определяет перевод между исходными данными и «повернутыми» данными.
martinatime
8

НикОтвет будет работать и для массива NxM с небольшой модификацией (в отличие от 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];

Один из способов думать об этом состоит в том, что вы переместили центр оси (0,0) из верхнего левого угла в верхний правый угол. Вы просто переносите из одного в другое.

Кевин Берридж
источник
6

Время - O (N), Пространство - 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;
        }
    }
}
user2793692
источник
Это не O (1). Это O (n).
Джейсон Остер
@JasonOster Я считаю, что это пространство O (1), так как оно не потребляет дополнительного пространства.
окопался
@ffledgling Моя ошибка. O (1) Пространственная сложность, да. O (N) сложность времени.
Джейсон Остер
Сложность пространства также равна O (n). Сложность пространства должна включать пространство размера входной переменной. careercup.com/question?id=14952322
Джейсон Хео
Как я могу изменить это, чтобы работать для вращения против часовой стрелки?
MD XF
5

Вот моя версия Ruby (обратите внимание, что значения не отображаются одинаково, но они все еще вращаются, как описано).

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
Майк Стоун
источник
4

Вот метод поворота в пространстве, по Java, только для квадрата. для не квадратного 2d массива вам все равно придется создавать новый массив.

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;
            }
        }
    }
}

код для вращения любого размера 2d массива путем создания нового массива:

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;
}
Джеймс Ю
источник
3

Реализация псевдокода +90 для dimple (например, транспонировать, затем перевернуть каждую строку) в 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;
}
mhawksey
источник
3

Вы можете сделать это в 3 простых шага :

1 ) Предположим, у нас есть матрица

   1 2 3
   4 5 6
   7 8 9

2 ) Возьмите транспонированную матрицу

   1 4 7
   2 5 8
   3 6 9

3 ) чередуйте строки, чтобы получить повернутую матрицу

   3 6 9
   2 5 8
   1 4 7

Исходный код Java для этого:

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 
Пратик Джоши
источник
2

Это моя реализация, в C, O (1) сложность памяти, поворот на месте, 90 градусов по часовой стрелке:

#include <stdio.h>

#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;
        }
    }
}
Паучок
источник
2

Вот версия Java:

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;
        }
    }
}

метод сначала вращает самый верхний слой, затем последовательно перемещается к внутреннему слою.

радий
источник
2

С линейной точки зрения рассмотрим матрицы:

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

Теперь возьми транспонирование

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

И рассмотрим действие A на B или B на A.
Соответственно:

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

Это расширяется для любой матрицы nxn. И быстро применить эту концепцию в коде:

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);
        }
    }
}
Мистер Некс
источник
2

C # код для поворота [n, m] 2D массивов на 90 градусов вправо

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
ustmaestro
источник
2

PHP:

<?php    
$a = array(array(1,2,3,4),array(5,6,7,8),array(9,0,1,2),array(3,4,5,6));
$b = array(); //result

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

Начиная с PHP5.6, транспонирование массива может быть выполнено со слабым array_map() вызова. Другими словами, столбцы преобразуются в строки.

Код: ( Демо )

$array = [
    [1, 2, 3, 4],
    [5, 6, 7, 8],
    [9, 0, 1, 2],
    [3, 4, 5, 6]
];
$transposed = array_map(null, ...$array);

$ Транспонировать:

[
    [1, 5, 9, 3],
    [2, 6, 0, 4],
    [3, 7, 1, 5],
    [4, 8, 2, 6]
]
James Lin
источник
1

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

X - размер массива, в котором находится графика.

турчанка
источник
1

#transpose является стандартным методом класса Array в Ruby, таким образом:

% 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]]

Реализация представляет собой функцию транспонирования n ^ 2, написанную на C. Вы можете увидеть ее здесь: http://www.ruby-doc.org/core-1.9.3/Array.html#method-i-transpose , выбрав «click» переключить источник "рядом с" транспонировать ".

Я помню лучше, чем O (n ^ 2) решения, но только для специально построенных матриц (таких как разреженные матрицы)

k00ka
источник
1

C-код для поворота матрицы на 90 градусов по часовой стрелке НА МЕСТЕ для любой матрицы M * N

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;i<flipTill;i++){
        for(j=0;j<i;j++){
            swapArrayElements(arr, i, j);
        }
    }

    temp = j+1;

    for(i = row>column?i:0; i<row; i++){
            for(j=row<column?temp:0; j<column; j++){
                swapArrayElements(arr, i, j);
            }
    }

    for(i=0;i<column;i++){
        for(j=0;j<row/2;j++){
            temp = arr[i][j];
            arr[i][j] = arr[i][row-j-1];
            arr[i][row-j-1] = temp;
        }
    }
}
rohitmb
источник
1

вот моя реализация на месте в C

void rotateRight(int matrix[][SIZE], int length) {

    int layer = 0;

    for (int layer = 0; layer < length / 2; ++layer) {

        int first = layer;
        int last = length - 1 - layer;

        for (int i = first; i < last; ++i) {

            int topline = matrix[first][i];
            int rightcol = matrix[i][last];
            int bottomline = matrix[last][length - layer - 1 - i];
            int leftcol = matrix[length - layer - 1 - i][first];

            matrix[first][i] = leftcol;
            matrix[i][last] = topline;
            matrix[last][length - layer - 1 - i] = rightcol;
            matrix[length - layer - 1 - i][first] = bottomline;
        }
    }
}
thiagoh
источник
1

Вот моя попытка поворота матрицы на 90 градусов, которая является двухшаговым решением в C. Сначала переставьте матрицу на месте, а затем поменяйте местами столбцы.

#define ROWS        5
#define COLS        5

void print_matrix_b(int B[][COLS], int rows, int cols) 
{
    for (int i = 0; i <= rows; i++) {
        for (int j = 0; j <=cols; j++) {
            printf("%d ", B[i][j]);
        }
        printf("\n");
    }
}

void swap_columns(int B[][COLS], int l, int r, int rows)
{
    int tmp;
    for (int i = 0; i <= rows; i++) {
        tmp = B[i][l];
        B[i][l] = B[i][r];
        B[i][r] = tmp;
    }
}


void matrix_2d_rotation(int B[][COLS], int rows, int cols)
{
    int tmp;
    // Transpose the matrix first
    for (int i = 0; i <= rows; i++) {
        for (int j = i; j <=cols; j++) {
            tmp = B[i][j];
            B[i][j] = B[j][i];
            B[j][i] = tmp;
        }
    }
    // Swap the first and last col and continue until
    // the middle.
    for (int i = 0; i < (cols / 2); i++)
        swap_columns(B, i, cols - i, rows);
}



int _tmain(int argc, _TCHAR* argv[])
{
    int B[ROWS][COLS] = { 
                  {1, 2, 3, 4, 5}, 
                      {6, 7, 8, 9, 10},
                          {11, 12, 13, 14, 15},
                          {16, 17, 18, 19, 20},
                          {21, 22, 23, 24, 25}
                        };

    matrix_2d_rotation(B, ROWS - 1, COLS - 1);

    print_matrix_b(B, ROWS - 1, COLS -1);
    return 0;
}
user1596193
источник
1

@dagorym: Ой человек. Я держался за это как хорошую головоломку «мне скучно, что я могу обдумать». Я придумал свой код транспонирования на месте, но попал сюда, чтобы найти ваш, в значительной степени идентичный моему ... ах, хорошо. Вот это в Ruby.

require 'pp'
n = 10
a = []
n.times { a << (1..n).to_a }

pp a

0.upto(n/2-1) do |i|
  i.upto(n-i-2) do |j|
    tmp             = a[i][j]
    a[i][j]         = a[n-j-1][i]
    a[n-j-1][i]     = a[n-i-1][n-j-1]
    a[n-i-1][n-j-1] = a[j][n-i-1]
    a[j][n-i-1]     = tmp
  end
end

pp a
Натан Фриц
источник
1
short normal[4][4] = {{8,4,7,5},{3,4,5,7},{9,5,5,6},{3,3,3,3}};

short rotated[4][4];

for (int r = 0; r < 4; ++r)
{
  for (int c = 0; c < 4; ++c)
  {
    rotated[r][c] = normal[c][3-r];
  }
}

Простой метод C ++, хотя в большом массиве будет большой объем памяти.

Уильям
источник
Среди всех этих ответов я нашел и протестировал этот компактный и достаточный для вращения
dlewin