受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²)时间和O(1)空间算法(没有任何变通方法和恶作剧的东西!)
旋转+90:
转置 反转每行
旋转-90:
方法一:
转置 反转每一列
方法二:
反转每行 转置
旋转180度:
方法一:旋转+90两次
方法2:反转每行，然后反转每列(转置)
旋转-180度:
方法一:旋转-90度2次
方法二:先反转每一列，再反转每一行
方法三:旋转+180，因为它们是相同的
其他回答
这是一个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
这是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;
}
这是我的实现，在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;
}
}
}
我的c#示例代码的伟大算法发送@dimple:
/* Author: Dudi,
* http://www.tutorialspoint.com/compile_csharp_online.php?PID=0Bw_CjBb95KQMYm5qU3VjVGNuZFU */
using System.IO;
using System;
class Program
{
static void Main()
{
Console.WriteLine("Rotating this matrix by 90+ degree:");
int[,] values=new int[3,3]{{1,2,3}, {4,5,6}, {7,8,9}};
//int[,] values=new int[4,4]{{101,102,103, 104}, {105,106, 107,108}, {109, 110, 111, 112}, {113, 114, 115, 116}};
print2dArray(ref values);
transpose2dArray(ref values);
//print2dArray(ref values);
reverse2dArray(ref values);
Console.WriteLine("Output:");
print2dArray(ref values);
}
static void print2dArray(ref int[,] matrix){
int nLen = matrix.GetLength(0);
int mLen = matrix.GetLength(1);
for(int n=0; n<nLen; n++){
for(int m=0; m<mLen; m++){
Console.Write(matrix[n,m] +"\t");
}
Console.WriteLine();
}
Console.WriteLine();
}
static void transpose2dArray(ref int[,] matrix){
int nLen = matrix.GetLength(0);
int mLen = matrix.GetLength(1);
for(int n=0; n<nLen; n++){
for(int m=0; m<mLen; m++){
if(n>m){
int tmp = matrix[n,m];
matrix[n,m] = matrix[m,n];
matrix[m,n] = tmp;
}
}
}
}
static void reverse2dArray(ref int[,] matrix){
int nLen = matrix.GetLength(0);
int mLen = matrix.GetLength(1);
for(int n=0; n<nLen; n++){
for(int m=0; m<mLen/2; m++){
int tmp = matrix[n,m];
matrix[n,m] = matrix[n, mLen-1-m];
matrix[n,mLen-1-m] = tmp;
}
}
}
}
/*
Rotating this matrix by 90+ degree:
1 2 3
4 5 6
7 8 9
Output:
7 4 1
8 5 2
9 6 3
*/
下面是我的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
