受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呢?
当前回答
我的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
*/
其他回答
这是一个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
Nick的答案也适用于NxM阵列，只需要做一点修改(与NxN相反)。
string[,] orig = new string[n, m];
string[,] rot = new string[m, n];
...
for ( int i=0; i < n; i++ )
for ( int j=0; j < m; j++ )
rot[j, n - i - 1] = orig[i, j];
考虑这个问题的一种方法是将轴(0,0)的中心从左上角移动到右上角。你只是简单地从一个转置到另一个。
这是我对矩阵90度旋转的尝试，这是c中的2步解决方案，首先转置矩阵，然后交换cols。
#define ROWS 5
#define COLS 5
void print_matrix_b(int B[][COLS], int rows, int cols)
{
for (int i = 0; i <= rows; i++) {
for (int j = 0; j <=cols; j++) {
printf("%d ", B[i][j]);
}
printf("\n");
}
}
void swap_columns(int B[][COLS], int l, int r, int rows)
{
int tmp;
for (int i = 0; i <= rows; i++) {
tmp = B[i][l];
B[i][l] = B[i][r];
B[i][r] = tmp;
}
}
void matrix_2d_rotation(int B[][COLS], int rows, int cols)
{
int tmp;
// Transpose the matrix first
for (int i = 0; i <= rows; i++) {
for (int j = i; j <=cols; j++) {
tmp = B[i][j];
B[i][j] = B[j][i];
B[j][i] = tmp;
}
}
// Swap the first and last col and continue until
// the middle.
for (int i = 0; i < (cols / 2); i++)
swap_columns(B, i, cols - i, rows);
}
int _tmain(int argc, _TCHAR* argv[])
{
int B[ROWS][COLS] = {
{1, 2, 3, 4, 5},
{6, 7, 8, 9, 10},
{11, 12, 13, 14, 15},
{16, 17, 18, 19, 20},
{21, 22, 23, 24, 25}
};
matrix_2d_rotation(B, ROWS - 1, COLS - 1);
print_matrix_b(B, ROWS - 1, COLS -1);
return 0;
}
试试我图书馆的算盘——常见的:
@Test
public void test_42519() throws Exception {
final IntMatrix matrix = IntMatrix.range(0, 16).reshape(4);
N.println("======= original =======================");
matrix.println();
// print out:
// [0, 1, 2, 3]
// [4, 5, 6, 7]
// [8, 9, 10, 11]
// [12, 13, 14, 15]
N.println("======= rotate 90 ======================");
matrix.rotate90().println();
// print out:
// [12, 8, 4, 0]
// [13, 9, 5, 1]
// [14, 10, 6, 2]
// [15, 11, 7, 3]
N.println("======= rotate 180 =====================");
matrix.rotate180().println();
// print out:
// [15, 14, 13, 12]
// [11, 10, 9, 8]
// [7, 6, 5, 4]
// [3, 2, 1, 0]
N.println("======= rotate 270 ======================");
matrix.rotate270().println();
// print out:
// [3, 7, 11, 15]
// [2, 6, 10, 14]
// [1, 5, 9, 13]
// [0, 4, 8, 12]
N.println("======= transpose =======================");
matrix.transpose().println();
// print out:
// [0, 4, 8, 12]
// [1, 5, 9, 13]
// [2, 6, 10, 14]
// [3, 7, 11, 15]
final IntMatrix bigMatrix = IntMatrix.range(0, 10000_0000).reshape(10000);
// It take about 2 seconds to rotate 10000 X 10000 matrix.
Profiler.run(1, 2, 3, "sequential", () -> bigMatrix.rotate90()).printResult();
// Want faster? Go parallel. 1 second to rotate 10000 X 10000 matrix.
final int[][] a = bigMatrix.array();
final int[][] c = new int[a[0].length][a.length];
final int n = a.length;
final int threadNum = 4;
Profiler.run(1, 2, 3, "parallel", () -> {
IntStream.range(0, n).parallel(threadNum).forEach(i -> {
for (int j = 0; j < n; j++) {
c[i][j] = a[n - j - 1][i];
}
});
}).printResult();
}
在JavaScript中实现dimple的+90伪代码(例如转置然后反转每一行):
function rotate90(a){
// transpose from http://www.codesuck.com/2012/02/transpose-javascript-array-in-one-line.html
a = Object.keys(a[0]).map(function (c) { return a.map(function (r) { return r[c]; }); });
// row reverse
for (i in a){
a[i] = a[i].reverse();
}
return a;
}
