受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呢?
当前回答
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;
}
其他回答
我的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
*/
试试我图书馆的算盘——常见的:
@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();
}
从线性的角度来看，考虑以下矩阵:
1 2 3 0 0 1
A = 4 5 6 B = 0 1 0
7 8 9 1 0 0
现在求A
1 4 7
A' = 2 5 8
3 6 9
考虑A'对B的作用，或B对A'的作用。 分别为:
7 4 1 3 6 9
A'B = 8 5 2 BA' = 2 5 8
9 6 3 1 4 7
这对任何nxn矩阵都是可展开的。 在代码中快速应用这个概念:
void swapInSpace(int** mat, int r1, int c1, int r2, int c2)
{
mat[r1][c1] ^= mat[r2][c2];
mat[r2][c2] ^= mat[r1][c1];
mat[r1][c1] ^= mat[r2][c2];
}
void transpose(int** mat, int size)
{
for (int i = 0; i < size; i++)
{
for (int j = (i + 1); j < size; j++)
{
swapInSpace(mat, i, j, j, i);
}
}
}
void rotate(int** mat, int size)
{
//Get transpose
transpose(mat, size);
//Swap columns
for (int i = 0; i < size / 2; i++)
{
for (int j = 0; j < size; j++)
{
swapInSpace(mat, i, j, size - (i + 1), j);
}
}
}
#!/usr/bin/env python
original = [ [1,2,3],
[4,5,6],
[7,8,9] ]
# Rotate matrix 90 degrees...
for i in map(None,*original[::-1]):
print str(i) + '\n'
这导致双方旋转90度(即。123(上面)现在是741(左边)。
这个Python解决方案是可行的，因为它使用了带负步的切片来反转行顺序(将7移到最上面)
original = [ [7,8,9],
[4,5,6],
[1,2,3] ]
然后，它使用map(以及隐含的标识函数，这是map以None作为第一个参数的结果)和*按顺序解包所有元素，重新组合列(即。第一个元素一起放在一个元组中，第二个元素一起放在一个元组中，以此类推)。你有效地得到得到返回如下重组:
original = [[7,8,9],
[4,5,6],
[1,2,3]]
JavaScript解决方案旋转矩阵90度的地方:
function rotateBy90(m) {
var length = m.length;
//for each layer of the matrix
for (var first = 0; first < length >> 1; first++) {
var last = length - 1 - first;
for (var i = first; i < last; i++) {
var top = m[first][i]; //store top
m[first][i] = m[last - i][first]; //top = left
m[last - i][first] = m[last][last - i]; //left = bottom
m[last][last - i] = m[i][last]; //bottom = right
m[i][last] = top; //right = top
}
}
return m;
}
