如何旋转二维数组?

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

更新:Nick的答案是最直接的，但是有没有比n²更好的方法呢?如果矩阵是10000x10000呢?

当前回答

正如我在上一篇文章中所说的，这里有一些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。对构造函数稍加更改，创建一个新数组并将值复制到该数组中，就可以将其整理出来。

2008-09-04 08:22:12

其他回答

PHP:

array_unshift($array, null);
$array = call_user_func_array("array_map", $array);

如果你需要旋转矩形二维阵列90度，在上面的代码之前或之后添加以下一行(取决于你需要的旋转方向):

$array = array_reverse($array);

2014-10-03 13:41:41

下面是PHP的递归方法:

$m = array();
            $m[0] = array('a', 'b', 'c');
            $m[1] = array('d', 'e', 'f');
            $m[2] = array('g', 'h', 'i');
            $newMatrix = array();

            function rotateMatrix($m, $i = 0, &$newMatrix)
            {
                foreach ($m as $chunk) {
                    $newChunk[] = $chunk[$i];
                }
                $newMatrix[] = array_reverse($newChunk);
                $i++;

                if ($i < count($m)) {
                    rotateMatrix($m, $i, $newMatrix);
                }
            }

            rotateMatrix($m, 0, $newMatrix);
            echo '<pre>';
            var_dump($newMatrix);
            echo '<pre>';

2014-02-24 02:29:50

这里有大量的好代码，但我只是想以几何形式展示，这样你就能更好地理解代码逻辑。以下是我的处理方法。

首先，不要把这和换位相混淆，换位是很容易的。

基本的想法是把它当作层，我们一次旋转一个层。

假设我们有一辆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

我们来分解它，首先旋转这四个角

1           4


13          16

然后我们旋转下面这个有点歪斜的菱形

然后是第二个斜菱形

这就搞定了外缘基本上我们一次做一个壳层直到

最后是中间的方块(如果是奇数则是最后一个不动的元素)

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]

2013-11-25 17:56:28

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

此代码基于Nick Berardi的帖子。

2009-07-07 14:37:25

这是我对矩阵90度旋转的尝试，这是c中的2步解决方案，首先转置矩阵，然后交换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;
}

2013-03-15 12:34:21

如何旋转二维数组?

推荐文章

最新文章

标签