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

这是我在C中的就地实现

void rotateRight(int matrix[][SIZE], int length) {

    int layer = 0;

    for (int layer = 0; layer < length / 2; ++layer) {

        int first = layer;
        int last = length - 1 - layer;

        for (int i = first; i < last; ++i) {

            int topline = matrix[first][i];
            int rightcol = matrix[i][last];
            int bottomline = matrix[last][length - layer - 1 - i];
            int leftcol = matrix[length - layer - 1 - i][first];

            matrix[first][i] = leftcol;
            matrix[i][last] = topline;
            matrix[last][length - layer - 1 - i] = rightcol;
            matrix[length - layer - 1 - i][first] = bottomline;
        }
    }
}

我想再补充一点细节。在这个答案中，关键概念被重复，节奏缓慢，故意重复。这里提供的解决方案在语法上不是最紧凑的，但是，它是为那些希望了解什么是矩阵旋转及其实现的人设计的。

首先，什么是矩阵?为了回答这个问题，矩阵就是一个宽度和高度相同的网格。注意，矩阵的宽度和高度可以不同，但是为了简单起见，本教程只考虑宽度和高度相等的矩阵(方阵)。是的，矩阵是矩阵的复数形式。

例如:2×2, 3×3或5×5。或者更通俗地说，N×N。2×2矩阵将有4个方框，因为2×2=4。一个5×5矩阵将有25个正方形，因为5×5=25。每个方格称为一个元素或项。我们将在下面的图表中用句点(.)表示每个元素:

2×2的矩阵

. .
. .

3×3矩阵

. . .
. . .
. . .

4×4矩阵

. . . .
. . . .
. . . .
. . . .

旋转一个矩阵意味着什么?让我们取一个2×2矩阵，在每个元素中放入一些数字，这样就可以观察到旋转:

0 1
2 3

将其旋转90度得到:

2 0
3 1

我们把整个矩阵向右转一次就像转汽车的方向盘一样。考虑将矩阵“倾斜”到右侧可能会有所帮助。我们想用Python写一个函数，取一个矩阵并向右旋转一次。函数签名将是:

def rotate(matrix):
    # Algorithm goes here.

矩阵将使用一个二维数组定义:

matrix = [
    [0,1],
    [2,3]
]

因此，第一个索引位置访问行。第二个索引位置访问列:

matrix[row][column]

我们将定义一个效用函数来打印一个矩阵。

def print_matrix(matrix):
    for row in matrix:
        print row

旋转矩阵的一种方法是一次旋转一层。但是什么是层呢?想象一个洋葱。就像洋葱的一层一层，随着每一层的移除，我们向中心移动。另一个类比是俄罗斯套娃或传递包裹的游戏。

矩阵的宽度和高度决定了该矩阵的层数。让我们为每一层使用不同的符号:

2×2矩阵有1层

. .
. .

3×3矩阵有两层

. . .
. x .
. . .

4×4矩阵有两层

. . . .
. x x .
. x x .
. . . .

5×5矩阵有3层

. . . . .
. x x x .
. x O x .
. x x x .
. . . . .

6×6矩阵有3层

. . . . . .
. x x x x .
. x O O x .
. x O O x .
. x x x x .
. . . . . .

7×7矩阵有4层

. . . . . . .
. x x x x x .
. x O O O x .
. x O - O x .
. x O O O x .
. x x x x x .
. . . . . . .

你可能会注意到，矩阵的宽度和高度增加一，并不总是增加层数。以上述矩阵为例，将层数和维度制成表格，我们可以看到层数每增加两个宽度和高度就会增加一次:

+-----+--------+
| N×N | Layers |
+-----+--------+
| 1×1 |      1 |
| 2×2 |      1 |
| 3×3 |      2 |
| 4×4 |      2 |
| 5×5 |      3 |
| 6×6 |      3 |
| 7×7 |      4 |
+-----+--------+

然而，并不是所有的层都需要旋转。1×1矩阵在旋转前后是相同的。无论整个矩阵有多大，中心1×1层在旋转前后总是相同的:

+-----+--------+------------------+
| N×N | Layers | Rotatable Layers |
+-----+--------+------------------+
| 1×1 |      1 |                0 |
| 2×2 |      1 |                1 |
| 3×3 |      2 |                1 |
| 4×4 |      2 |                2 |
| 5×5 |      3 |                2 |
| 6×6 |      3 |                3 |
| 7×7 |      4 |                3 |
+-----+--------+------------------+

给定N×N矩阵，我们如何以编程方式确定我们需要旋转的层数?如果我们将宽度或高度除以2，忽略余数，我们会得到以下结果。

+-----+--------+------------------+---------+
| N×N | Layers | Rotatable Layers |   N/2   |
+-----+--------+------------------+---------+
| 1×1 |      1 |                0 | 1/2 = 0 |
| 2×2 |      1 |                1 | 2/2 = 1 |
| 3×3 |      2 |                1 | 3/2 = 1 |
| 4×4 |      2 |                2 | 4/2 = 2 |
| 5×5 |      3 |                2 | 5/2 = 2 |
| 6×6 |      3 |                3 | 6/2 = 3 |
| 7×7 |      4 |                3 | 7/2 = 3 |
+-----+--------+------------------+---------+

注意到N/2是如何匹配需要旋转的层数的?有时可旋转层数比矩阵的总层数少一层。当最内层只由一个元素(即1×1矩阵)形成时，就会发生这种情况，因此不需要旋转。它只是被忽略了。

毫无疑问，我们在函数中需要这个信息来旋转一个矩阵，所以让我们现在添加它:

def rotate(matrix):
    size = len(matrix)
    # Rotatable layers only.
    layer_count = size / 2

现在我们知道什么是层，以及如何确定实际需要旋转的层数，我们如何隔离单个层以便我们可以旋转它?首先，我们检查一个矩阵，从最外层，向内，到最内层。5×5矩阵总共有三层，其中两层需要旋转:

. . . . .
. x x x .
. x O x .
. x x x .
. . . . .

让我们先看看列。定义最外层的列的位置，假设我们从0开始计数，是0和4:

+--------+-----------+
| Column | 0 1 2 3 4 |
+--------+-----------+
|        | . . . . . |
|        | . x x x . |
|        | . x O x . |
|        | . x x x . |
|        | . . . . . |
+--------+-----------+

0和4也是最外层的行位置。

+-----+-----------+
| Row |           |
+-----+-----------+
|   0 | . . . . . |
|   1 | . x x x . |
|   2 | . x O x . |
|   3 | . x x x . |
|   4 | . . . . . |
+-----+-----------+

这将总是这样，因为宽度和高度是相同的。因此，我们可以用两个值(而不是四个)定义一个层的列和行位置。

向内移动到第二层，列的位置为1和3。是的，你猜对了，对于行也是一样的。当向内移动到下一层时，我们必须同时增加和减少行和列的位置，理解这一点很重要。

+-----------+---------+---------+---------+
|   Layer   |  Rows   | Columns | Rotate? |
+-----------+---------+---------+---------+
| Outermost | 0 and 4 | 0 and 4 | Yes     |
| Inner     | 1 and 3 | 1 and 3 | Yes     |
| Innermost | 2       | 2       | No      |
+-----------+---------+---------+---------+

因此，为了检查每一层，我们需要一个循环，其中有递增和递减计数器，表示从最外层开始向内移动。我们称之为“层循环”。

def rotate(matrix):
    size = len(matrix)
    layer_count = size / 2

    for layer in range(0, layer_count):
        first = layer
        last = size - first - 1
        print 'Layer %d: first: %d, last: %d' % (layer, first, last)

# 5x5 matrix
matrix = [
    [ 0, 1, 2, 3, 4],
    [ 5, 6, 6, 8, 9],
    [10,11,12,13,14],
    [15,16,17,18,19],
    [20,21,22,23,24]
]

rotate(matrix)

上面的代码循环遍历需要旋转的任何层的(行和列)位置。

Layer 0: first: 0, last: 4
Layer 1: first: 1, last: 3

现在我们有了一个循环，提供了每一层的行和列的位置。变量第一个和最后一个标识第一个和最后一个行和列的索引位置。回到行表和列表:

+--------+-----------+
| Column | 0 1 2 3 4 |
+--------+-----------+
|        | . . . . . |
|        | . x x x . |
|        | . x O x . |
|        | . x x x . |
|        | . . . . . |
+--------+-----------+

+-----+-----------+
| Row |           |
+-----+-----------+
|   0 | . . . . . |
|   1 | . x x x . |
|   2 | . x O x . |
|   3 | . x x x . |
|   4 | . . . . . |
+-----+-----------+

所以我们可以在矩阵的层中导航。现在我们需要一种在层内导航的方法，这样我们就可以在该层周围移动元素。注意，元素从不从一个层“跳转”到另一个层，但它们确实在各自的层内移动。

旋转图层中的每个元素将旋转整个图层。旋转矩阵中的所有层将旋转整个矩阵。这句话很重要，所以在继续读下去之前请尽量理解它。

现在，我们需要一种实际移动元素的方法，即旋转每个元素，然后是层，最终是矩阵。为了简单起见，我们将恢复到一个3x3矩阵-它有一个可旋转的层。

0 1 2
3 4 5
6 7 8

我们的层循环提供了第一个和最后一个列的索引，以及第一个和最后一个行:

+-----+-------+
| Col | 0 1 2 |
+-----+-------+
|     | 0 1 2 |
|     | 3 4 5 |
|     | 6 7 8 |
+-----+-------+

+-----+-------+
| Row |       |
+-----+-------+
|   0 | 0 1 2 |
|   1 | 3 4 5 |
|   2 | 6 7 8 |
+-----+-------+

因为我们的矩阵总是方阵，我们只需要两个变量，第一个和最后一个，因为行和列的下标位置是相同的。

def rotate(matrix):
    size = len(matrix)
    layer_count = size / 2

    # Our layer loop i=0, i=1, i=2
    for layer in range(0, layer_count):

        first = layer
        last = size - first - 1
        
        # We want to move within a layer here.

第一个和最后一个变量可以很容易地用于引用矩阵的四个角。这是因为角本身可以使用第一个和最后一个的各种排列来定义(不需要对这些变量进行减法、加法或偏移):

+---------------+-------------------+-------------+
| Corner        | Position          | 3x3 Values  |
+---------------+-------------------+-------------+
| top left      | (first, first)    | (0,0)       |
| top right     | (first, last)     | (0,2)       |
| bottom right  | (last, last)      | (2,2)       |
| bottom left   | (last, first)     | (2,0)       |
+---------------+-------------------+-------------+

出于这个原因，我们从外层的四个角开始旋转——我们先旋转它们。让我们用*突出显示它们。

* 1 *
3 4 5
* 7 *

我们要把每个*和它右边的*交换。所以让我们继续打印我们的角，只使用第一和最后的不同排列来定义:

def rotate(matrix):
    size = len(matrix)
    layer_count = size / 2
    for layer in range(0, layer_count):

        first = layer
        last = size - first - 1

        top_left = (first, first)
        top_right = (first, last)
        bottom_right = (last, last)
        bottom_left = (last, first)

        print 'top_left: %s' % (top_left)
        print 'top_right: %s' % (top_right)
        print 'bottom_right: %s' % (bottom_right)
        print 'bottom_left: %s' % (bottom_left)

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

rotate(matrix)

输出应该是:

top_left: (0, 0)
top_right: (0, 2)
bottom_right: (2, 2)
bottom_left: (2, 0)

现在我们可以很容易地在我们的层循环中交换每个角:

def rotate(matrix):
    size = len(matrix)
    layer_count = size / 2
    for layer in range(0, layer_count):
        
        first = layer
        last = size - first - 1

        top_left = matrix[first][first]
        top_right = matrix[first][last]
        bottom_right = matrix[last][last]
        bottom_left = matrix[last][first]

        # bottom_left -> top_left
        matrix[first][first] = bottom_left
        # top_left -> top_right
        matrix[first][last] = top_left
        # top_right -> bottom_right
        matrix[last][last] = top_right
        # bottom_right -> bottom_left
        matrix[last][first] = bottom_right


print_matrix(matrix)
print '---------'
rotate(matrix)
print_matrix(matrix)

转角前矩阵:

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

转角后矩阵:

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

太棒了!我们已经成功地旋转了矩阵的每个角。但是，我们没有旋转每层中间的元素。显然，我们需要一种在层内迭代的方法。

问题是，到目前为止，我们函数中唯一的循环(我们的层循环)在每次迭代时都移动到下一层。由于我们的矩阵只有一个可旋转的层，层循环在旋转角后退出。让我们看看一个更大的5×5矩阵(其中两个层需要旋转)会发生什么。函数代码略去，与前文相同:

matrix = [
[0, 1, 2, 3, 4],
[5, 6, 7, 8, 9],
[10, 11, 12, 13, 14],
[15, 16, 17, 18, 19],
[20, 21, 22, 23, 24]
]
print_matrix(matrix)
print '--------------------'
rotate(matrix)
print_matrix(matrix)

输出结果为:

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

It shouldn’t be a surprise that the corners of the outermost layer have been rotated, but, you may also notice the corners of the next layer (inwards) have also been rotated. This makes sense. We’ve written code to navigate through layers and also to rotate the corners of each layer. This feels like progress, but unfortunately we must take a step back. It’s just no good moving onto the next layer until the previous (outer) layer has been fully rotated. That is, until each element in the layer has been rotated. Rotating only the corners won’t do!

深呼吸。我们需要另一个循环。一个嵌套循环。新的嵌套循环将使用第一个和最后一个变量，加上一个偏移量来在层内导航。我们将这个新循环称为“element loop”。元素循环将访问顶部一行的每个元素、右侧一行的每个元素、底部一行的每个元素和左侧一行的每个元素。

沿着顶部行向前移动需要列 要递增的索引。 向右移动要求行索引为 递增。 沿着底部向后移动需要列 要递减的索引。 向左侧移动要求行索引为 递减。

这听起来很复杂，但它很简单，因为我们为实现上述目标所增加和减少的次数在矩阵的四个边都是相同的。例如:

移动第一行的一个元素。 向右移动一个元素。 沿着最下面一行向后移动一个元素。 把一个元素移到左边。

这意味着我们可以将单个变量与第一个和最后一个变量结合使用来在一个层中移动。注意从上一行移动到右一行都需要递增，这可能会有所帮助。当沿着底部和左侧向上向后移动时，两者都需要递减。

def rotate(matrix):
    size = len(matrix)
    layer_count = size / 2
    
    # Move through layers (i.e. layer loop).
    for layer in range(0, layer_count):
        
            first = layer
            last = size - first - 1

            # Move within a single layer (i.e. element loop).
            for element in range(first, last):
            
                offset = element - first

                # 'element' increments column (across right)
                top = (first, element)
                # 'element' increments row (move down)
                right_side = (element, last)
                # 'last-offset' decrements column (across left)
                bottom = (last, last-offset)
                # 'last-offset' decrements row (move up)
                left_side = (last-offset, first)

                print 'top: %s' % (top)
                print 'right_side: %s' % (right_side)
                print 'bottom: %s' % (bottom)
                print 'left_side: %s' % (left_side)

现在我们只需要将顶部分配给右侧，右侧分配给底部，底部分配给左侧，左侧分配给顶部。把这些放在一起，我们得到:

def rotate(matrix):
    size = len(matrix)
    layer_count = size / 2

    for layer in range(0, layer_count):
        first = layer
        last = size - first - 1

        for element in range(first, last):
            offset = element - first

            top = matrix[first][element]
            right_side = matrix[element][last]
            bottom = matrix[last][last-offset]
            left_side = matrix[last-offset][first]

            matrix[first][element] = left_side
            matrix[element][last] = top
            matrix[last][last-offset] = right_side
            matrix[last-offset][first] = bottom

给定矩阵:

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

旋转函数的结果是:

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

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

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

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

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

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

下面是一个原地旋转的数组，而不是使用一个全新的数组来保存结果。我已经停止了数组的初始化和输出。这只适用于正方形数组，但它们可以是任何大小。内存开销等于数组中一个元素的大小，因此您可以对任意大的数组进行旋转。

int a[4][4];
int n = 4;
int tmp;
for (int i = 0; i < n / 2; i++)
{
    for (int j = i; j < n - i - 1; j++)
    {
        tmp             = a[i][j];
        a[i][j]         = a[j][n-i-1];
        a[j][n-i-1]     = a[n-i-1][n-j-1];
        a[n-i-1][n-j-1] = a[n-j-1][i];
        a[n-j-1][i]     = tmp;
    }
}