你如何旋转二维数组?

algorithm matrix multidimensional-array

284349 观看

30回复

35150 作者的声誉

灵感来自Raymond Chen的帖子,假设你有一个4x4二维数组,写一个旋转90度的函数。Raymond链接到伪代码的解决方案,但我希望看到一些现实世界的东西。

[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怎么办?

作者: swilliams 的来源 发布者: 2008 年 9 月 3 日

回应 (30)


137

46386 作者的声誉

决定

这是在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;
}
作者: Nick Berardi 发布者: 03.09.2008 08:41

5

33449 作者的声誉

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

The output:

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
作者: Mike Stone 发布者: 03.09.2008 08:59

8

4238 作者的声誉

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.

作者: Kevin Berridge 发布者: 03.09.2008 09:04

10

9268 作者的声誉

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.

作者: nsanders 发布者: 03.09.2008 09:13

35

44867 作者的声誉

As I said in my previous post, here's some code in C# that implements an O(1) matrix rotation for any size matrix. For brevity and readability there's no error checking or range checking. The code:

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

OK, I'll put my hand up, it doesn't actually do any modifications to the original array when rotating. But, in an OO system that doesn't matter as long as the object looks like it's been rotated to the clients of the class. At the moment, the Matrix class uses references to the original array data so changing any value of m1 will also change m2 and m3. A small change to the constructor to create a new array and copy the values to it will sort that out.

作者: Skizz 发布者: 04.09.2008 08:22

69

3192 作者的声誉

Here is one that does the rotation in place instead of using a completely new array to hold the result. I've left off initialization of the array and printing it out. This only works for square arrays but they can be of any size. Memory overhead is equal to the size of one element of the array so you can do the rotation of as large an array as you want.

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;
    }
}
作者: dagorym 发布者: 04.09.2008 06:12

1

1128 作者的声誉

@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
作者: Nathan Fritz 发布者: 07.09.2008 05:41

23

196786 作者的声誉

Whilst rotating the data in place might be necessary (perhaps to update the physically stored representation), it becomes simpler and possibly more performant to add a layer of indirection onto the array access, perhaps an interface:

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

If your Matrix already implements this interface, then it can be rotated via a decorator class like this:

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

Rotating +90/-90/180 degrees, flipping horizontally/vertically and scaling can all be achieved in this fashion as well.

Performance would need to be measured in your specific scenario. However the O(n^2) operation has now been replaced with an O(1) call. It's a virtual method call which is slower than direct array access, so it depends upon how frequently the rotated array is used after rotation. If it's used once, then this approach would definitely win. If it's rotated then used in a long-running system for days, then in-place rotation might perform better. It also depends whether you can accept the up-front cost.

As with all performance issues, measure, measure, measure!

作者: Drew Noakes 发布者: 11.10.2008 10:33

124

64012 作者的声誉

Python:

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

Cheap, I know.

And counterclockwise:

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

How this works: (Requested in comments)

zip(*original) will swap axes of 2d arrays by stacking corresponding items from lists into new lists. (The * operator tells the function to distribute the contained lists into arguments)

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

The [::-1] statement reverses array elements (please see Extended Slices).

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

Finally, combining the two will result in the rotation transformation.

The change in placement of [::-1] will reverse lists in different levels of the matrix.

作者: recursive 发布者: 30.01.2009 04:12

1

0 作者的声誉

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 ++方法,在大数组中会有很大的内存开销。

作者: William 发布者: 04.06.2009 02:12

17

0 作者的声誉

This a better version of it in Java: I've made it for a matrix with a different width and height

  • h is here the height of the matrix after rotating
  • w is here the width of the matrix after rotating

 

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

This code is based on Nick Berardi's post.

作者: Martijn Courteaux 发布者: 07.07.2009 02:37

2

9888 作者的声誉

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);
    }
}
?>
作者: James Lin 发布者: 29.06.2010 02:12

17

28089 作者的声誉

Ruby-way: .transpose.map &:reverse

作者: Nakilon 发布者: 26.08.2010 01:43

370

536 作者的声誉

O(n ^ 2)时间和O(1)空间算法(没有任何变通方法和手帕很好的东西!)

旋转+90:

  1. 颠倒
  2. 反转每一行

旋转-90:

方法1:

  1. 颠倒
  2. 反转每一列

方法2:

  1. 反转每一行
  2. 颠倒

旋转+180:

方法1:旋转+90两次

方法2:反转每一行然后反转每一列(Transpose)

旋转-180:

方法1:旋转-90两次

方法2:反转每列,然后反转每一行

方法3:旋转+180,因为它们是相同的

作者: dimple 发布者: 29.12.2011 07:00

1

11 作者的声誉

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

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

作者: Turk 发布者: 29.12.2011 02:13

4

113 作者的声誉

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;
}
作者: James Yu 发布者: 14.03.2012 10:52

2

1686 作者的声誉

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

#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;
        }
    }
}
作者: Spidey 发布者: 05.04.2012 01:42

1

1029 作者的声誉

#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)

作者: k00ka 发布者: 27.07.2012 09:05

1

127 作者的声誉

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;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 发布者: 25.02.2013 06:18

1

102 作者的声誉

Here is my attempt for matrix 90 deg rotation which is a 2 step solution in C. First transpose the matrix in place and then swap the cols.

#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 发布者: 15.03.2013 12:34

2

11 作者的声誉

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.

作者: radium 发布者: 21.05.2013 02:50

1

4264 作者的声誉

here is my In Place implementation in 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 发布者: 13.08.2013 05:47

3

1648 作者的声誉

Implementation of dimple's +90 pseudocode (e.g. 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;
}
作者: mhawksey 发布者: 15.08.2013 09:42

38

344 作者的声誉

There are tons of good code here but I just want to show what's going on geometrically so you can understand the code logic a little better. Here is how I would approach this.

first of all, do not confuse this with transposition which is very easy..

the basica idea is to treat it as layers and we rotate one layer at a time..

say we have a 4x4

1   2   3   4
5   6   7   8
9   10  11  12
13  14  15  16

after we rotate it clockwise by 90 we get

13  9   5   1
14  10  6   2   
15  11  7   3
16  12  8   4

so let's decompose this, first we rotate the 4 corners essentially

1           4


13          16

then we rotate the following diamond which is sort of askew

    2
            8
9       
        15

and then the 2nd skewed diamond

        3
5           
            12
    14

so that takes care of the outer edge so essentially we do that one shell at a time until

finally the middle square (or if it's odd just the final element which does not move)

6   7
10  11

so now let's figure out the indices of each layer, assume we always work with the outermost layer, we are doing

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

so on and so on until we are halfway through the edge

so in general the pattern is

[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]
作者: tweaking 发布者: 25.11.2013 05:56

6

1 作者的声誉

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;
        }
    }
}
作者: user2793692 发布者: 21.01.2014 05:47

2

158 作者的声誉

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 n x n 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);
        }
    }
}
作者: Mr. Nex 发布者: 12.10.2014 12:47

13

1053 作者的声誉

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 e.g. 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);

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

This code assumes an array of nested arrays, where each inner array is a row.

The method allows you to read (or write) elements (even in random order) as if the array has been rotated or transformed. Now just pick the right function to call, probably by reference, and away you go!

The concept can be extended to apply transformations additively (and non-destructively) through the accessor methods. Including arbitrary angle rotations and scaling.

作者: Jason Oster 发布者: 15.10.2014 04:35

2

588 作者的声誉

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

Result:

    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 发布者: 19.02.2015 03:22

3

2437 作者的声誉

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

Output:

1 2 3 
4 5 6 
7 8 9 

3 6 9 
2 5 8 
1 4 7 
作者: Prateek Joshi 发布者: 30.12.2015 06:09

163

4234 作者的声誉

我想补充一点细节。在这个答案中,重复关键概念,步伐缓慢且有意重复。这里提供的解决方案不是语法上最紧凑的,但是,它适用于那些希望了解矩阵旋转是什么以及由此产生的实现的人。

首先,什么是矩阵?出于本答案的目的,矩阵只是宽度和高度相同的网格。注意,矩阵的宽度和高度可以不同,但​​为简单起见,本教程仅考虑宽度和高度相等的矩阵方阵)。是的,矩阵矩阵的复数。

示例矩阵是: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

旋转矩阵的一种方法是一次一层地进行。但什么是层?想想洋葱。就像洋葱的层一样,每一层被移除,我们都会向中心移动。其他类比是Matryoshka娃娃或传递包裹的游戏。

矩阵的宽度和高度决定了该矩阵中的层数。让我们为每一层使用不同的符号:

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 .
. . . . . . .

您可能会注意到,将矩阵的宽度和高度递增1并不总是会增加层数。采用上述矩阵并将图层和尺寸制成表格,我们看到每两个宽度和高度增量的层数增加一次:

+-----+--------+
| 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 |
+-----+--------+------------------+

Given N×N matrix, how can we programmatically determine the number of layers we need to rotate? If we divide the width or height by two and ignore the remainder we get the following results.

+-----+--------+------------------+---------+
| 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 |
+-----+--------+------------------+---------+

Notice how N/2 matches the number of layers that need to be rotated? Sometimes the number of rotatable layers is one less the total number of layers in the matrix. This occurs when the innermost layer is formed of only one element (i.e. a 1×1 matrix) and therefore need not be rotated. It simply gets ignored.

We will undoubtedly need this information in our function to rotate a matrix, so let’s add it now:

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

Now we know what layers are and how to determine the number of layers that actually need rotating, how do we isolate a single layer so we can rotate it? Firstly, we inspect a matrix from the outermost layer, inwards, to the innermost layer. A 5×5 matrix has three layers in total and two layers that need rotating:

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

Let’s look at columns first. The position of the columns defining the outermost layer, assuming we count from 0, are 0 and 4:

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

0 and 4 are also the positions of the rows for the outermost layer.

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

This will always be the case since the width and height are the same. Therefore we can define the column and row positions of a layer with just two values (rather than four).

向内移动到第二层,列的位置是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

我们现在有一个循环,提供每层的行和列的位置。变量firstlast标识第一个和最后一个行和列的索引位置。回头参考我们的行和列表:

+--------+-----------+
| 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 | . . . . . |
+-----+-----------+

所以我们可以浏览矩阵的各个层。现在我们需要一种在图层中导航的方法,以便我们可以在该图层周围移动元素。请注意,元素永远不会从一个层“跳跃”到另一个层,但它们会在各自的层内移动。

旋转图层中的每个元素会旋转整个图层。旋转矩阵中的所有层会旋转整个矩阵。这句话非常重要,所以请在继续之前尽力了解它。

现在,我们需要一种实际移动元素的方法,即旋转每个元素,然后旋转图层,最后旋转矩阵。为简单起见,我们将恢复为3x3矩阵 - 具有一个可旋转层。

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 |
+-----+-------+

Because our matrices are always square, we need just two variables, first and last, since index positions are the same for rows and columns.

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.

The variables first and last can easily be used to reference the four corners of a matrix. This is because the corners themselves can be defined using various permutations of first and last (with no subtraction, addition or offset of those variables):

+---------------+-------------------+-------------+
| 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)       |
+---------------+-------------------+-------------+

For this reason, we start our rotation at the outer four corners — we’ll rotate those first. Let’s highlight them with *.

* 1 *
3 4 5
* 7 *

We want to swap each * with the * to the right of it. So let’s go ahead a print out our corners defined using only various permutations of first and 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)

Output should be:

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

Now we could quite easily swap each of the corners from within our layer loop:

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)

Matrix before rotating corners:

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

Matrix after rotating corners:

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

Great! We have successfully rotated each corner of the matrix. But, we haven’t rotated the elements in the middle of each layer. Clearly we need a way of iterating within a layer.

The problem is, the only loop in our function so far (our layer loop), moves to the next layer on each iteration. Since our matrix has only one rotatable layer, the layer loop exits after rotating only the corners. Let’s look at what happens with a larger, 5×5 matrix (where two layers need rotating). The function code has been omitted, but it remains the same as above:

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)

The output is:

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

最外层的角已经旋转应该不足为奇,但是,您也可能注意到下一层(向内)的角也已经旋转。这是有道理的。我们编写了代码来浏览图层并旋转每个图层的角。这感觉就像进步一样,但遗憾的是我们必须退后一步。在前一个(外部)层完全旋转之前,移动到下一层是没有好处的。也就是说,直到图层中的每个元素都被旋转。只旋转角落不行!

深吸一口气。我们需要另一个循环。嵌套循环不少。新的嵌套循环将使用firstlast变量,以及在图层中导航的偏移量。我们将这个新循环称为'元素循环'。元素循环将访问顶行的每个元素,每个元素在右侧,每个元素沿底行,每个元素在左侧。

  • 沿顶行向前移动需要增加列索引。
  • 向右移动需要递增行索引。
  • 沿底部向后移动需要减少列索引。
  • 向上移动需要递减行索引。

这听起来很复杂,但它变得容易,因为我们增加和减少以实现上述的次数在矩阵的所有四边保持相同。例如:

  • 在顶行移动1个元素。
  • 向右移动1个元素。
  • 沿底行向后移动1个元素。
  • 向左移动1个元素。

这意味着我们可以将单个变量与firstlast变量结合使用以在图层中移动。可能有助于注意,在顶行和右侧移动都需要递增。沿着底部向上移动而向上移动时,两者都需要递减。

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 

Our rotate function results in:

6,  3,  0  
7,  4,  1  
8,  5,  2  
作者: Jack 发布者: 16.02.2016 04:50
32x32