受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度旋转的尝试，这是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;
}
其他回答
在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)
我的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
*/
这个解决方案不关心正方形或矩形的尺寸，你可以旋转4x5或5x4甚至4x4，它也不关心大小。 注意，这种实现在每次调用rotate90方法时都会创建一个新数组，它根本不会改变原始数组。
public static void main(String[] args) {
int[][] a = new int[][] {
{ 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 9, 0, 1, 2 },
{ 3, 4, 5, 6 },
{ 7, 8, 9, 0 }
};
int[][] rotate180 = rotate90(rotate90(a));
print(rotate180);
}
static int[][] rotate90(int[][] a) {
int[][] ret = new int[a[0].length][a.length];
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a[i].length; j++) {
ret[j][a.length - i - 1] = a[i][j];
}
}
return ret;
}
static void print(int[][] array) {
for (int i = 0; i < array.length; i++) {
System.out.print("[");
for (int j = 0; j < array[i].length; j++) {
System.out.print(array[i][j]);
System.out.print(" ");
}
System.out.println("]");
}
}
已经有很多答案了，我发现两个声称O(1)时间复杂度。真正的O(1)算法是保持数组存储不变，并改变索引其元素的方式。这里的目标是不消耗额外的内存，也不需要额外的时间来迭代数据。
旋转90度，-90度和180度是简单的转换，只要你知道你的2D数组中有多少行和列就可以执行;要将任何向量旋转90度，交换轴并与Y轴相反。对于-90度，交换轴和X轴。对于180度，两个坐标轴都是负的，不交换。
进一步的转换是可能的，例如通过独立地否定轴来水平和/或垂直地镜像。
这可以通过访问器方法来实现。下面的例子是JavaScript函数，但是这些概念同样适用于所有语言。
//按列/行顺序获取数组元素 var getArray2d =函数(a, x, y) { 返回一个[y] [x]; }; / /演示 Var arr = [ [5,4,6]， [1,7,9]， [- 2,11,0]， [8,21， -3]， [3， -1, 2] ]; Var newar = []; arr[0]. foreach (() => newarr。push(新数组(arr.length))); For (var I = 0;I < newar .length;我+ +){ For (var j = 0;J < newarr[0].length;j + +) { newarr[i][j] = getArray2d(arr, i, j); ｝ ｝ console.log (newarr);
// Get an array element rotated 90 degrees clockwise function getArray2dCW(a, x, y) { var t = x; x = y; y = a.length - t - 1; return a[y][x]; } //demo var arr = [ [5, 4, 6], [1, 7, 9], [-2, 11, 0], [8, 21, -3], [3, -1, 2] ]; var newarr = []; arr[0].forEach(() => newarr.push(new Array(arr.length))); for (var i = 0; i < newarr[0].length; i++) { for (var j = 0; j < newarr.length; j++) { newarr[j][i] = getArray2dCW(arr, i, j); } } console.log(newarr);
// Get an array element rotated 90 degrees counter-clockwise function getArray2dCCW(a, x, y) { var t = x; x = a[0].length - y - 1; y = t; return a[y][x]; } //demo var arr = [ [5, 4, 6], [1, 7, 9], [-2, 11, 0], [8, 21, -3], [3, -1, 2] ]; var newarr = []; arr[0].forEach(() => newarr.push(new Array(arr.length))); for (var i = 0; i < newarr[0].length; i++) { for (var j = 0; j < newarr.length; j++) { newarr[j][i] = getArray2dCCW(arr, i, j); } } console.log(newarr);
// Get an array element rotated 180 degrees function getArray2d180(a, x, y) { x = a[0].length - x - 1; y = a.length - y - 1; return a[y][x]; } //demo var arr = [ [5, 4, 6], [1, 7, 9], [-2, 11, 0], [8, 21, -3], [3, -1, 2] ]; var newarr = []; arr.forEach(() => newarr.push(new Array(arr[0].length))); for (var i = 0; i < newarr[0].length; i++) { for (var j = 0; j < newarr.length; j++) { newarr[j][i] = getArray2d180(arr, i, j); } } console.log(newarr);
这段代码假设有一个嵌套数组的数组，其中每个内部数组都是一行。
该方法允许您读取(或写入)元素(甚至是随机顺序)，就像数组已经旋转或转换一样。现在只要选择正确的函数来调用，可能是通过引用，然后就可以了!
这个概念可以扩展为通过访问器方法附加地(非破坏性地)应用转换。包括任意角度旋转和缩放。
我只用一个循环就能做到。时间复杂度看起来像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]
