受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呢?
当前回答
在原地顺时针90度旋转使用矢量矢量..
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
//Rotate a Matrix by 90 degrees
void rotateMatrix(vector<vector<int> > &matrix){
int n=matrix.size();
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
swap(matrix[i][j],matrix[j][i]);
}
}
for(int i=0;i<n;i++){
reverse(matrix[i].begin(),matrix[i].end());
}
}
int main(){
int n;
cout<<"enter the size of the matrix:"<<endl;
while (cin >> n) {
vector< vector<int> > m;
cout<<"enter the elements"<<endl;
for (int i = 0; i < n; i++) {
m.push_back(vector<int>(n));
for (int j = 0; j < n; j++)
scanf("%d", &m[i][j]);
}
cout<<"the rotated matrix is:"<<endl;
rotateMatrix(m);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
cout << m[i][j] << ' ';
cout << endl;
}
}
return 0;
}
其他回答
我想再补充一点细节。在这个答案中，关键概念被重复，节奏缓慢，故意重复。这里提供的解决方案在语法上不是最紧凑的，但是，它是为那些希望了解什么是矩阵旋转及其实现的人设计的。
首先，什么是矩阵?为了回答这个问题，矩阵就是一个宽度和高度相同的网格。注意，矩阵的宽度和高度可以不同，但是为了简单起见，本教程只考虑宽度和高度相等的矩阵(方阵)。是的，矩阵是矩阵的复数形式。
例如: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
这是一个空间旋转方法，由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;
}
Python:
rotated = list(zip(*original[::-1]))
和逆时针方向:
rotated_ccw = list(zip(*original))[::-1]
这是如何工作的:
Zip (*original)将通过将列表中的对应项堆叠到新的列表中来交换2d数组的轴。(*操作符告诉函数将包含的列表分布到参数中)
>>> list(zip(*[[1,2,3],[4,5,6],[7,8,9]]))
[[1,4,7],[2,5,8],[3,6,9]]
语句[::-1]反转数组元素(请参阅扩展切片或这个问题):
>>> [[1,2,3],[4,5,6],[7,8,9]][::-1]
[[7,8,9],[4,5,6],[1,2,3]]
最后，将两者结合就得到了旋转变换。
改变[::-1]的位置将使列表在矩阵的不同层次上颠倒。
这是我的实现，在C, O(1)内存复杂度，原地旋转，顺时针90度:
#include <stdio.h>
#define M_SIZE 5
static void initMatrix();
static void printMatrix();
static void rotateMatrix();
static int m[M_SIZE][M_SIZE];
int main(void){
initMatrix();
printMatrix();
rotateMatrix();
printMatrix();
return 0;
}
static void initMatrix(){
int i, j;
for(i = 0; i < M_SIZE; i++){
for(j = 0; j < M_SIZE; j++){
m[i][j] = M_SIZE*i + j + 1;
}
}
}
static void printMatrix(){
int i, j;
printf("Matrix\n");
for(i = 0; i < M_SIZE; i++){
for(j = 0; j < M_SIZE; j++){
printf("%02d ", m[i][j]);
}
printf("\n");
}
printf("\n");
}
static void rotateMatrix(){
int r, c;
for(r = 0; r < M_SIZE/2; r++){
for(c = r; c < M_SIZE - r - 1; c++){
int tmp = m[r][c];
m[r][c] = m[M_SIZE - c - 1][r];
m[M_SIZE - c - 1][r] = m[M_SIZE - r - 1][M_SIZE - c - 1];
m[M_SIZE - r - 1][M_SIZE - c - 1] = m[c][M_SIZE - r - 1];
m[c][M_SIZE - r - 1] = tmp;
}
}
}
当前所有的解决方案都有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]);
}
免责声明:我实际上并没有测试这个。让我们玩打虫游戏吧!
