受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呢?


当前回答

这是一个如今被高估的面试问题。

我的建议是:不要让面试官用他们关于解决这个问题的疯狂建议把你弄糊涂了。使用白板绘制输入数组的索引,然后绘制输出数组的索引。旋转前后的列分度示例如下:

30 --> 00
20 --> 01
10 --> 02
00 --> 03

31 --> 10
21 --> 11
11 --> 12
01 --> 13

注意旋转后的数字模式。

下面提供了一个简洁的Java解决方案。经过测试,它是有效的:

 Input:
    M A C P 
    B N L D 
    Y E T S 
    I W R Z 

    Output:
    I Y B M 
    W E N A 
    R T L C 
    Z S D P 

/**
 * (c) @author "G A N MOHIM"
 * Oct 3, 2015
 * RotateArrayNintyDegree.java
 */
package rotatearray;

public class RotateArrayNintyDegree {

    public char[][] rotateArrayNinetyDegree(char[][] input) {
        int k; // k is used to generate index for output array

        char[][] output = new char[input.length] [input[0].length];

        for (int i = 0; i < input.length; i++) {
            k = 0;
            for (int j = input.length-1; j >= 0; j--) {
                output[i][k] = input[j][i]; // note how i is used as column index, and j as row
                k++;
            }
        }

        return output;
    }

    public void printArray(char[][] charArray) {
        for (int i = 0; i < charArray.length; i++) {
            for (int j = 0; j < charArray[0].length; j++) {
                System.out.print(charArray[i][j] + " ");
            }
            System.out.println();
        }


    }

    public static void main(String[] args) {
        char[][] input = 
                { {'M', 'A', 'C', 'P'},
                  {'B', 'N', 'L', 'D'},
                  {'Y', 'E', 'T', 'S'},
                  {'I', 'W', 'R', 'Z'}
                };

        char[][] output = new char[input.length] [input[0].length];

        RotateArrayNintyDegree rotationObj = new RotateArrayNintyDegree();
        rotationObj.printArray(input);

        System.out.println("\n");
        output = rotationObj.rotateArrayNinetyDegree(input);
        rotationObj.printArray(output);

    }

}

其他回答

#!/usr/bin/env python

original = [ [1,2,3],
             [4,5,6],
             [7,8,9] ]

# Rotate matrix 90 degrees...
for i in map(None,*original[::-1]):
    print str(i) + '\n'

这导致双方旋转90度(即。123(上面)现在是741(左边)。

这个Python解决方案是可行的,因为它使用了带负步的切片来反转行顺序(将7移到最上面)

original = [ [7,8,9],
             [4,5,6],
             [1,2,3] ]

然后,它使用map(以及隐含的标识函数,这是map以None作为第一个参数的结果)和*按顺序解包所有元素,重新组合列(即。第一个元素一起放在一个元组中,第二个元素一起放在一个元组中,以此类推)。你有效地得到得到返回如下重组:

original = [[7,8,9],
             [4,5,6],
             [1,2,3]]

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

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

对于i:= 0到X 对于j:= 0到X做 [j][i]:= graphic2[X-i][j]

X是图形所在数组的大小。

O(n²)时间和O(1)空间算法(没有任何变通方法和恶作剧的东西!)

旋转+90:

转置 反转每行

旋转-90:

方法一:

转置 反转每一列

方法二:

反转每行 转置

旋转180度:

方法一:旋转+90两次

方法2:反转每行,然后反转每列(转置)

旋转-180度:

方法一:旋转-90度2次

方法二:先反转每一列,再反转每一行

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