受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(n^2)开销作为临时空间(这不包括那些肮脏的OOP骗子!)这里有一个内存占用为O(1)的解决方案,将矩阵原地右转90度。该死的延展性,这玩意儿跑得很快!

#include <algorithm>
#include <cstddef>

// Rotates an NxN matrix of type T 90 degrees to the right.
template <typename T, size_t N>
void rotate_matrix(T (&matrix)[N][N])
{
    for(size_t i = 0; i < N; ++i)
        for(size_t j = 0; j <= (N-i); ++j)
            std::swap(matrix[i][j], matrix[j][i]);
}

免责声明:我实际上并没有测试这个。让我们玩打虫游戏吧!

其他回答

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

这是一个Javascript解决方案:

const transpose = m => m[0].map((x,i) => m.map(x => x[i]));

a: // original matrix
123
456
789

transpose(a).reverse(); // rotate 90 degrees counter clockwise 
369
258
147

transpose(a.slice().reverse()); // rotate 90 degrees clockwise 
741
852
963

transpose(transpose(a.slice().reverse()).slice().reverse())
// rotate 180 degrees 
987
654
321
    public static void rotateMatrix(int[,] matrix)
    {
        //C#, to rotate an N*N matrix in place
        int n = matrix.GetLength(0);
        int layers =  n / 2;
        int temp, temp2;

        for (int i = 0; i < layers; i++) // for a 5 * 5 matrix, layers will be 2, since at layer three there would be only one element, (2,2), and we do not need to rotate it with itself 
        {
            int offset = 0;
            while (offset < n - 2 * i - 1)
            {
                // top right <- top left 
                temp = matrix[i + offset, n - i - 1]; //top right value when offset is zero
                matrix[i + offset, n - i - 1] = matrix[i, i + offset];   

                //bottom right <- top right 
                temp2 = matrix[n - i - 1, n - i - 1 - offset]; //bottom right value when offset is zero
                matrix[n - i - 1, n - i - 1 - offset] = temp;  

                //bottom left <- bottom right 
                temp = matrix[n - i - 1 - offset, i];
                matrix[n - i - 1 - offset, i] = temp2;  

                //top left <- bottom left 
                matrix[i, i + offset] = temp; 

                offset++;
            }
        }
    }

已经有很多答案了,我发现两个声称O(1)时间复杂度。真正的O(1)算法是保持数组存储不变,并改变索引其元素的方式。这里的目标是不消耗额外的内存,也不需要额外的时间来迭代数据。

旋转90度,-90度和180度是简单的转换,只要你知道你的2D数组中有多少行和列就可以执行;要将任何向量旋转90度,交换轴并与Y轴相反。对于-90度,交换轴和X轴。对于180度,两个坐标轴都是负的,不交换。

进一步的转换是可能的,例如通过独立地否定轴来水平和/或垂直地镜像。

这可以通过访问器方法来实现。下面的例子是JavaScript函数,但是这些概念同样适用于所有语言。

//按列/行顺序获取数组元素 var getArray2d =函数(a, x, y) { 返回一个[y] [x]; }; / /演示 Var arr = [ [5,4,6], [1,7,9], [- 2,11,0], [8,21, -3], [3, -1, 2] ]; Var newar = []; arr[0]. foreach (() => newarr。push(新数组(arr.length))); For (var I = 0;I < newar .length;我+ +){ 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);

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

该方法允许您读取(或写入)元素(甚至是随机顺序),就像数组已经旋转或转换一样。现在只要选择正确的函数来调用,可能是通过引用,然后就可以了!

这个概念可以扩展为通过访问器方法附加地(非破坏性地)应用转换。包括任意角度旋转和缩放。

/* 90-degree clockwise:
   temp_array         = left_col
   left_col           = bottom_row
   bottom_row         = reverse(right_col)
   reverse(right_col) = reverse(top_row)
   reverse(top_row)   = temp_array
*/
void RotateClockwise90(int ** arr, int lo, int hi) {

  if (lo >= hi) 
    return;

  for (int i=lo; i<hi; i++) {
    int j = lo+hi-i;
    int temp   = arr[i][lo];
    arr[i][lo] = arr[hi][i];
    arr[hi][i] = arr[j][hi];
    arr[j][hi] = arr[lo][j];
    arr[lo][j] = temp;
  }

  RotateClockwise90(arr, lo+1, hi-1);
}