如何旋转一个二维数组？

Question

如何旋转一个二维数组？

359

受雷蒙德·陈的帖子的启发，假设你有一个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^2更好的方法呢？如果矩阵是10000x10000呢？

- swilliams

114

你怎么可能只用少于n^2的步骤？所有元素都必须读取和设置，而且有n^2个元素。 - erikkallen

9

您的n是多少？您没有说明2D数组是否为正方形（一般情况下并非如此！例如，向量是具有一个维度为1的矩阵），但是您似乎在暗示n是宽度和高度，并且因此有n²个元素。更合理的做法是让n成为元素数量，其中n=w×h。 - niXar

1

以下是一种快速的方法：存储行和列索引（例如 i 和 j）。转置只需要常数时间（只需交换索引即可 :)）。您可以使用旋转进行相同的操作（玩转索引）。 - mrk

4

如果n^2不可行，您可以创建一个接口来访问每个元素。然后，给定(i,j)，对(i,j)应用旋转操作以访问旋转后的元素并返回其值。这可能不是最佳解决方案，但是可以使用。 - Confuse

1

我认为你仍然可以在小于N^2的时间内完成它。但是，需要使用更复杂的数据结构。也许是某种双向链表？ - Younes Nj

显示剩余8条评论

64个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jason Oster · Answer 1

已经有很多答案了，我发现有两个声称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);

这段代码假设有一组嵌套数组，其中每个内部数组是一行。

该方法允许您读取（或写入）元素（即使以随机顺序），就像数组已经被旋转或变换一样。现在只需要选择正确的函数进行调用，可能通过引用，然后就可以开始了！

该概念可以通过存取方法进行叠加变换（并且不会破坏原有数据）。包括任意角度旋转和缩放。

- nsanders · Answer 2

已经有一些人提供了涉及创建新数组的示例。

还有其他几件事需要考虑：

(a) 不要实际移动数据，只需以不同方式遍历“旋转”数组即可。

(b) 在原地进行旋转可能会有点棘手。您需要一点临时空间（大约等于一个行或列的大小）。有一篇古老的ACM论文介绍如何进行原地转置(http://doi.acm.org/10.1145/355719.355729)，但它们的示例代码是由goto语句组成的且很难理解的FORTRAN。

补充说明：

http://doi.acm.org/10.1145/355611.355612 是另一种据说更好的原地转置算法。

- Kevin Berridge · Answer 3

Nick的回答也适用于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）从左上角移动到了右上角。你只是从一个位置转换到另一个位置。

- user2793692 · Answer 4

时间复杂度 - 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;
        }
    }
}

- Kapil · Answer 5

一个常用的方法是将二维数组顺时针或逆时针旋转。

clockwise rotate

first reverse up to down, then swap the symmetry

1 2 3     7 8 9     7 4 1
4 5 6  => 4 5 6  => 8 5 2
7 8 9     1 2 3     9 6 3

void rotate(vector<vector<int> > &matrix) {
    reverse(matrix.begin(), matrix.end());
    for (int i = 0; i < matrix.size(); ++i) {
        for (int j = i + 1; j < matrix[i].size(); ++j)
            swap(matrix[i][j], matrix[j][i]);
    }
}

anticlockwise rotate

first reverse left to right, then swap the symmetry

1 2 3     3 2 1     3 6 9
4 5 6  => 6 5 4  => 2 5 8
7 8 9     9 8 7     1 4 7

void anti_rotate(vector<vector<int> > &matrix) {
    for (auto vi : matrix) reverse(vi.begin(), vi.end());
    for (int i = 0; i < matrix.size(); ++i) {
        for (int j = i + 1; j < matrix[i].size(); ++j)
            swap(matrix[i][j], matrix[j][i]);
    }
}

- Mike Stone · Answer 6

这是我的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))

输出结果:

- Prateek Joshi · Answer 7

你可以通过以下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();
        }
    }
}

输出：

- James Yu · Answer 8

这里有一个针对正方形数组的java内置旋转方法。对于非正方形的二维数组，你无论如何都需要创建新数组。

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

- Michael Dunne · Answer 9

在Python中：

import numpy as np

a = np.array(
    [
        [1, 2, 3, 4],
        [5, 6, 7, 8],
        [9, 0, 1, 2],
        [3, 4, 5, 6]
    ]
)

print(a)
print(b[::-1, :].T)

- mhawksey · Answer 10

在JavaScript中实现dimple的+90伪代码（例如转置，然后反转每一行）：

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