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


当前回答

可以做递归相当干净,这里是我的实现在golang!

在没有额外内存的情况下递归地旋转go golang中的NXN矩阵

func rot90(a [][]int) {
    n := len(a)
    if n == 1 {
        return
    }
    for i := 0; i < n; i++ {
        a[0][i], a[n-1-i][n-1] = a[n-1-i][n-1], a[0][i]
    }
    rot90(a[1:])
}

其他回答

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

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

输出:

1 5 9 3 
2 6 0 4 
3 7 1 5 
4 8 2 6 

4 3 2 1 
8 7 6 5 
2 1 0 9 
6 5 4 3
private static int[][] rotate(int[][] matrix, int n) {
    int[][] rotated = new int[n][n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            rotated[i][j] = matrix[n-j-1][i];
        }
    }
    return rotated;
}

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

旋转+90:

转置 反转每行

旋转-90:

方法一:

转置 反转每一列

方法二:

反转每行 转置

旋转180度:

方法一:旋转+90两次

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

旋转-180度:

方法一:旋转-90度2次

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

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

这是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的帖子。