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


当前回答

我只用一个循环就能做到。时间复杂度看起来像O(K)其中K是数组中的所有元素。 下面是我用JavaScript做的:

首先,我们用一个数组来表示n^2矩阵。然后,像这样迭代它:

/**
 * Rotates matrix 90 degrees clockwise
 * @param arr: the source array
 * @param n: the array side (array is square n^2)
 */
function rotate (arr, n) {
  var rotated = [], indexes = []

  for (var i = 0; i < arr.length; i++) {
    if (i < n)
      indexes[i] = i * n + (n - 1)
    else
      indexes[i] = indexes[i - n] - 1

    rotated[indexes[i]] = arr[i]
  }
  return rotated
}

基本上,我们转换源数组下标:

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

然后,使用这个转换后的索引数组,我们将实际值放在最终旋转的数组中。

下面是一些测试用例:

//n=3
rotate([
  1, 2, 3,
  4, 5, 6,
  7, 8, 9], 3))

//result:
[7, 4, 1,
 8, 5, 2,
 9, 6, 3]


//n=4
rotate([
  1,  2,  3,  4,
  5,  6,  7,  8,
  9,  10, 11, 12,
  13, 14, 15, 16], 4))

//result:
[13,  9,  5,  1,
 14, 10,  6,  2,
 15, 11,  7,  3,
 16, 12,  8,  4]


//n=5
rotate([
  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], 5))

//result:
[21, 16, 11,  6,  1, 
 22, 17, 12,  7,  2, 
 23, 18, 13,  8,  3, 
 24, 19, 14,  9,  4, 
 25, 20, 15, 10,  5]

其他回答

这是一个空间旋转方法,由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;
}

我只用一个循环就能做到。时间复杂度看起来像O(K)其中K是数组中的所有元素。 下面是我用JavaScript做的:

首先,我们用一个数组来表示n^2矩阵。然后,像这样迭代它:

/**
 * Rotates matrix 90 degrees clockwise
 * @param arr: the source array
 * @param n: the array side (array is square n^2)
 */
function rotate (arr, n) {
  var rotated = [], indexes = []

  for (var i = 0; i < arr.length; i++) {
    if (i < n)
      indexes[i] = i * n + (n - 1)
    else
      indexes[i] = indexes[i - n] - 1

    rotated[indexes[i]] = arr[i]
  }
  return rotated
}

基本上,我们转换源数组下标:

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

然后,使用这个转换后的索引数组,我们将实际值放在最终旋转的数组中。

下面是一些测试用例:

//n=3
rotate([
  1, 2, 3,
  4, 5, 6,
  7, 8, 9], 3))

//result:
[7, 4, 1,
 8, 5, 2,
 9, 6, 3]


//n=4
rotate([
  1,  2,  3,  4,
  5,  6,  7,  8,
  9,  10, 11, 12,
  13, 14, 15, 16], 4))

//result:
[13,  9,  5,  1,
 14, 10,  6,  2,
 15, 11,  7,  3,
 16, 12,  8,  4]


//n=5
rotate([
  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], 5))

//result:
[21, 16, 11,  6,  1, 
 22, 17, 12,  7,  2, 
 23, 18, 13,  8,  3, 
 24, 19, 14,  9,  4, 
 25, 20, 15, 10,  5]

PHP:

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

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

$array = array_reverse($array);

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

在Eigen (c++)中:

Eigen::Matrix2d mat;
mat <<  1, 2,
        3, 4;
std::cout << mat << "\n\n";

Eigen::Matrix2d r_plus_90 = mat.transpose().rowwise().reverse();
std::cout << r_plus_90 << "\n\n";

Eigen::Matrix2d r_minus_90 = mat.transpose().colwise().reverse();
std::cout << r_minus_90 << "\n\n";

Eigen::Matrix2d r_180 = mat.colwise().reverse().rowwise().reverse(); // +180 same as -180
std::cout << r_180 << "\n\n";

输出:

1 2
3 4

3 1
4 2

2 4
1 3

4 3
2 1