受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呢?
受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呢?
当前回答
试试我图书馆的算盘——常见的:
@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();
}
其他回答
这是将数组旋转90度的简单C代码。希望这能有所帮助。
#include <stdio.h>
void main(){
int arr[3][4] = {85, 2, 85, 4,
85, 6, 7, 85,
9, 85, 11, 12};
int arr1[4][3];
int i = 0, j = 0;
for(i=0;i<4;i++){
int k = 2;//k = (number of columns in the new array arr1 - 1)
for(j=0;j<3;j++){
arr1[i][j]=arr[k][i];
k--;
}
}
int l, m;
for(l=0;l<4;l++){
for(m=0;m<3;m++){
printf("%d ", arr1[l][m]);
}
printf("\n");
}
}//end main
我只用一个循环就能做到。时间复杂度看起来像O(K)其中K是数组中的所有元素。 下面是我用JavaScript做的:
首先,我们用一个数组来表示n^2矩阵。然后,像这样迭代它:
/**
* Rotates matrix 90 degrees clockwise
* @param arr: the source array
* @param n: the array side (array is square n^2)
*/
function rotate (arr, n) {
var rotated = [], indexes = []
for (var i = 0; i < arr.length; i++) {
if (i < n)
indexes[i] = i * n + (n - 1)
else
indexes[i] = indexes[i - n] - 1
rotated[indexes[i]] = arr[i]
}
return rotated
}
基本上,我们转换源数组下标:
[0,1,2,3,4,5,6,7,8] => [2,5,8,1,4,7,0,3 6]
然后,使用这个转换后的索引数组,我们将实际值放在最终旋转的数组中。
下面是一些测试用例:
//n=3
rotate([
1, 2, 3,
4, 5, 6,
7, 8, 9], 3))
//result:
[7, 4, 1,
8, 5, 2,
9, 6, 3]
//n=4
rotate([
1, 2, 3, 4,
5, 6, 7, 8,
9, 10, 11, 12,
13, 14, 15, 16], 4))
//result:
[13, 9, 5, 1,
14, 10, 6, 2,
15, 11, 7, 3,
16, 12, 8, 4]
//n=5
rotate([
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], 5))
//result:
[21, 16, 11, 6, 1,
22, 17, 12, 7, 2,
23, 18, 13, 8, 3,
24, 19, 14, 9, 4,
25, 20, 15, 10, 5]
这是一个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
你可以通过3个简单步骤做到这一点:
1)假设我们有一个矩阵
1 2 3
4 5 6
7 8 9
2)求矩阵的转置
1 4 7
2 5 8
3 6 9
3)交换行得到旋转矩阵
3 6 9
2 5 8
1 4 7
Java源代码:
public class MyClass {
public static void main(String args[]) {
Demo obj = new Demo();
/*initial matrix to rotate*/
int[][] matrix = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } };
int[][] transpose = new int[3][3]; // matrix to store transpose
obj.display(matrix); // initial matrix
obj.rotate(matrix, transpose); // call rotate method
System.out.println();
obj.display(transpose); // display the rotated matix
}
}
class Demo {
public void rotate(int[][] mat, int[][] tran) {
/* First take the transpose of the matrix */
for (int i = 0; i < mat.length; i++) {
for (int j = 0; j < mat.length; j++) {
tran[i][j] = mat[j][i];
}
}
/*
* Interchange the rows of the transpose matrix to get rotated
* matrix
*/
for (int i = 0, j = tran.length - 1; i != j; i++, j--) {
for (int k = 0; k < tran.length; k++) {
swap(i, k, j, k, tran);
}
}
}
public void swap(int a, int b, int c, int d, int[][] arr) {
int temp = arr[a][b];
arr[a][b] = arr[c][d];
arr[c][d] = temp;
}
/* Method to display the matrix */
public void display(int[][] arr) {
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length; j++) {
System.out.print(arr[i][j] + " ");
}
System.out.println();
}
}
}
输出:
1 2 3
4 5 6
7 8 9
3 6 9
2 5 8
1 4 7
在python中:
import numpy as np
a = np.array(
[
[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 0, 1, 2],
[3, 4, 5, 6]
]
)
print(a)
print(b[::-1, :].T)