受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#代码，可以为任何大小的矩阵实现O(1)矩阵旋转。为了简洁性和可读性，没有错误检查或范围检查。代码:
static void Main (string [] args)
{
int [,]
// create an arbitrary matrix
m = {{0, 1}, {2, 3}, {4, 5}};
Matrix
// create wrappers for the data
m1 = new Matrix (m),
m2 = new Matrix (m),
m3 = new Matrix (m);
// rotate the matricies in various ways - all are O(1)
m1.RotateClockwise90 ();
m2.Rotate180 ();
m3.RotateAnitclockwise90 ();
// output the result of transforms
System.Diagnostics.Trace.WriteLine (m1.ToString ());
System.Diagnostics.Trace.WriteLine (m2.ToString ());
System.Diagnostics.Trace.WriteLine (m3.ToString ());
}
class Matrix
{
enum Rotation
{
None,
Clockwise90,
Clockwise180,
Clockwise270
}
public Matrix (int [,] matrix)
{
m_matrix = matrix;
m_rotation = Rotation.None;
}
// the transformation routines
public void RotateClockwise90 ()
{
m_rotation = (Rotation) (((int) m_rotation + 1) & 3);
}
public void Rotate180 ()
{
m_rotation = (Rotation) (((int) m_rotation + 2) & 3);
}
public void RotateAnitclockwise90 ()
{
m_rotation = (Rotation) (((int) m_rotation + 3) & 3);
}
// accessor property to make class look like a two dimensional array
public int this [int row, int column]
{
get
{
int
value = 0;
switch (m_rotation)
{
case Rotation.None:
value = m_matrix [row, column];
break;
case Rotation.Clockwise90:
value = m_matrix [m_matrix.GetUpperBound (0) - column, row];
break;
case Rotation.Clockwise180:
value = m_matrix [m_matrix.GetUpperBound (0) - row, m_matrix.GetUpperBound (1) - column];
break;
case Rotation.Clockwise270:
value = m_matrix [column, m_matrix.GetUpperBound (1) - row];
break;
}
return value;
}
set
{
switch (m_rotation)
{
case Rotation.None:
m_matrix [row, column] = value;
break;
case Rotation.Clockwise90:
m_matrix [m_matrix.GetUpperBound (0) - column, row] = value;
break;
case Rotation.Clockwise180:
m_matrix [m_matrix.GetUpperBound (0) - row, m_matrix.GetUpperBound (1) - column] = value;
break;
case Rotation.Clockwise270:
m_matrix [column, m_matrix.GetUpperBound (1) - row] = value;
break;
}
}
}
// creates a string with the matrix values
public override string ToString ()
{
int
num_rows = 0,
num_columns = 0;
switch (m_rotation)
{
case Rotation.None:
case Rotation.Clockwise180:
num_rows = m_matrix.GetUpperBound (0);
num_columns = m_matrix.GetUpperBound (1);
break;
case Rotation.Clockwise90:
case Rotation.Clockwise270:
num_rows = m_matrix.GetUpperBound (1);
num_columns = m_matrix.GetUpperBound (0);
break;
}
StringBuilder
output = new StringBuilder ();
output.Append ("{");
for (int row = 0 ; row <= num_rows ; ++row)
{
if (row != 0)
{
output.Append (", ");
}
output.Append ("{");
for (int column = 0 ; column <= num_columns ; ++column)
{
if (column != 0)
{
output.Append (", ");
}
output.Append (this [row, column].ToString ());
}
output.Append ("}");
}
output.Append ("}");
return output.ToString ();
}
int [,]
// the original matrix
m_matrix;
Rotation
// the current view of the matrix
m_rotation;
}
好的，我把手举起来，当旋转时，它实际上不会对原始数组做任何修改。但是，在面向对象系统中，只要对象看起来像是被旋转到类的客户端，这就无关紧要了。目前，Matrix类使用对原始数组数据的引用，因此改变m1的任何值也将改变m2和m3。对构造函数稍加更改，创建一个新数组并将值复制到该数组中，就可以将其整理出来。
其他回答
为新手程序员，在纯c++。(宝蓝的东西)
#include<iostream.h>
#include<conio.h>
int main()
{
clrscr();
int arr[10][10]; // 2d array that holds input elements
int result[10][10]; //holds result
int m,n; //rows and columns of arr[][]
int x,y; //rows and columns of result[][]
int i,j; //loop variables
int t; //temporary , holds data while conversion
cout<<"Enter no. of rows and columns of array: ";
cin>>m>>n;
cout<<"\nEnter elements of array: \n\n";
for(i = 0; i < m; i++)
{
for(j = 0; j<n ; j++)
{
cin>>arr[i][j]; // input array elements from user
}
}
//rotating matrix by +90 degrees
x = n ; //for non-square matrix
y = m ;
for(i = 0; i < x; i++)
{ t = m-1; // to create required array bounds
for(j = 0; j < y; j++)
{
result[i][j] = arr[t][i];
t--;
}
}
//print result
cout<<"\nRotated matrix is: \n\n";
for(i = 0; i < x; i++)
{
for(j = 0; j < y; j++)
{
cout<<result[i][j]<<" ";
}
cout<<"\n";
}
getch();
return 0;
}
基于社区wiki算法和这个转置数组的SO答案，这里是一个Swift 4版本，可以逆时针旋转一些2D数组90度。这里假设matrix是一个2D数组:
func rotate(matrix: [[Int]]) -> [[Int]] {
let transposedPoints = transpose(input: matrix)
let rotatedPoints = transposedPoints.map{ Array($0.reversed()) }
return rotatedPoints
}
fileprivate func transpose<T>(input: [[T]]) -> [[T]] {
if input.isEmpty { return [[T]]() }
let count = input[0].count
var out = [[T]](repeating: [T](), count: count)
for outer in input {
for (index, inner) in outer.enumerated() {
out[index].append(inner)
}
}
return out
}
#!/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]]
矩阵转置和旋转(+/-90，+/-180)的C代码
支持方阵和非方阵，具有原位和复制功能 支持2D数组和带有逻辑行/cols的1D指针 单元测试;有关使用示例，请参阅测试 测试gcc -std=c90 -Wall -pedantic, MSVC17
`
#include <stdlib.h>
#include <memory.h>
#include <assert.h>
/*
Matrix transpose & rotate (+/-90, +/-180)
Supports both 2D arrays and 1D pointers with logical rows/cols
Supports square and non-square matrices, has in-place and copy features
See tests for examples of usage
tested gcc -std=c90 -Wall -pedantic, MSVC17
*/
typedef int matrix_data_t; /* matrix data type */
void transpose(const matrix_data_t* src, matrix_data_t* dst, int rows, int cols);
void transpose_inplace(matrix_data_t* data, int n );
void rotate(int direction, const matrix_data_t* src, matrix_data_t* dst, int rows, int cols);
void rotate_inplace(int direction, matrix_data_t* data, int n);
void reverse_rows(matrix_data_t* data, int rows, int cols);
void reverse_cols(matrix_data_t* data, int rows, int cols);
/* test/compare fn */
int test_cmp(const matrix_data_t* lhs, const matrix_data_t* rhs, int rows, int cols );
/* TESTS/USAGE */
void transpose_test() {
matrix_data_t sq3x3[9] = { 0,1,2,3,4,5,6,7,8 };/* 3x3 square, odd length side */
matrix_data_t sq3x3_cpy[9];
matrix_data_t sq3x3_2D[3][3] = { { 0,1,2 },{ 3,4,5 },{ 6,7,8 } };/* 2D 3x3 square */
matrix_data_t sq3x3_2D_copy[3][3];
/* expected test values */
const matrix_data_t sq3x3_orig[9] = { 0,1,2,3,4,5,6,7,8 };
const matrix_data_t sq3x3_transposed[9] = { 0,3,6,1,4,7,2,5,8};
matrix_data_t sq4x4[16]= { 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 };/* 4x4 square, even length*/
const matrix_data_t sq4x4_orig[16] = { 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 };
const matrix_data_t sq4x4_transposed[16] = { 0,4,8,12,1,5,9,13,2,6,10,14,3,7,11,15 };
/* 2x3 rectangle */
const matrix_data_t r2x3_orig[6] = { 0,1,2,3,4,5 };
const matrix_data_t r2x3_transposed[6] = { 0,3,1,4,2,5 };
matrix_data_t r2x3_copy[6];
matrix_data_t r2x3_2D[2][3] = { {0,1,2},{3,4,5} }; /* 2x3 2D rectangle */
matrix_data_t r2x3_2D_t[3][2];
/* matrix_data_t r3x2[6] = { 0,1,2,3,4,5 }; */
matrix_data_t r3x2_copy[6];
/* 3x2 rectangle */
const matrix_data_t r3x2_orig[6] = { 0,1,2,3,4,5 };
const matrix_data_t r3x2_transposed[6] = { 0,2,4,1,3,5 };
matrix_data_t r6x1[6] = { 0,1,2,3,4,5 }; /* 6x1 */
matrix_data_t r6x1_copy[6];
matrix_data_t r1x1[1] = { 0 }; /*1x1*/
matrix_data_t r1x1_copy[1];
/* 3x3 tests, 2D array tests */
transpose_inplace(sq3x3, 3); /* transpose in place */
assert(!test_cmp(sq3x3, sq3x3_transposed, 3, 3));
transpose_inplace(sq3x3, 3); /* transpose again */
assert(!test_cmp(sq3x3, sq3x3_orig, 3, 3));
transpose(sq3x3, sq3x3_cpy, 3, 3); /* transpose copy 3x3*/
assert(!test_cmp(sq3x3_cpy, sq3x3_transposed, 3, 3));
transpose((matrix_data_t*)sq3x3_2D, (matrix_data_t*)sq3x3_2D_copy, 3, 3); /* 2D array transpose/copy */
assert(!test_cmp((matrix_data_t*)sq3x3_2D_copy, sq3x3_transposed, 3, 3));
transpose_inplace((matrix_data_t*)sq3x3_2D_copy, 3); /* 2D array transpose in place */
assert(!test_cmp((matrix_data_t*)sq3x3_2D_copy, sq3x3_orig, 3, 3));
/* 4x4 tests */
transpose_inplace(sq4x4, 4); /* transpose in place */
assert(!test_cmp(sq4x4, sq4x4_transposed, 4,4));
transpose_inplace(sq4x4, 4); /* transpose again */
assert(!test_cmp(sq4x4, sq4x4_orig, 3, 3));
/* 2x3,3x2 tests */
transpose(r2x3_orig, r2x3_copy, 2, 3);
assert(!test_cmp(r2x3_copy, r2x3_transposed, 3, 2));
transpose(r3x2_orig, r3x2_copy, 3, 2);
assert(!test_cmp(r3x2_copy, r3x2_transposed, 2,3));
/* 2D array */
transpose((matrix_data_t*)r2x3_2D, (matrix_data_t*)r2x3_2D_t, 2, 3);
assert(!test_cmp((matrix_data_t*)r2x3_2D_t, r2x3_transposed, 3,2));
/* Nx1 test, 1x1 test */
transpose(r6x1, r6x1_copy, 6, 1);
assert(!test_cmp(r6x1_copy, r6x1, 1, 6));
transpose(r1x1, r1x1_copy, 1, 1);
assert(!test_cmp(r1x1_copy, r1x1, 1, 1));
}
void rotate_test() {
/* 3x3 square */
const matrix_data_t sq3x3[9] = { 0,1,2,3,4,5,6,7,8 };
const matrix_data_t sq3x3_r90[9] = { 6,3,0,7,4,1,8,5,2 };
const matrix_data_t sq3x3_180[9] = { 8,7,6,5,4,3,2,1,0 };
const matrix_data_t sq3x3_l90[9] = { 2,5,8,1,4,7,0,3,6 };
matrix_data_t sq3x3_copy[9];
/* 3x3 square, 2D */
matrix_data_t sq3x3_2D[3][3] = { { 0,1,2 },{ 3,4,5 },{ 6,7,8 } };
/* 4x4, 2D */
matrix_data_t sq4x4[4][4] = { { 0,1,2,3 },{ 4,5,6,7 },{ 8,9,10,11 },{ 12,13,14,15 } };
matrix_data_t sq4x4_copy[4][4];
const matrix_data_t sq4x4_r90[16] = { 12,8,4,0,13,9,5,1,14,10,6,2,15,11,7,3 };
const matrix_data_t sq4x4_l90[16] = { 3,7,11,15,2,6,10,14,1,5,9,13,0,4,8,12 };
const matrix_data_t sq4x4_180[16] = { 15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0 };
matrix_data_t r6[6] = { 0,1,2,3,4,5 }; /* rectangle with area of 6 (1x6,2x3,3x2, or 6x1) */
matrix_data_t r6_copy[6];
const matrix_data_t r1x6_r90[6] = { 0,1,2,3,4,5 };
const matrix_data_t r1x6_l90[6] = { 5,4,3,2,1,0 };
const matrix_data_t r1x6_180[6] = { 5,4,3,2,1,0 };
const matrix_data_t r2x3_r90[6] = { 3,0,4,1,5,2 };
const matrix_data_t r2x3_l90[6] = { 2,5,1,4,0,3 };
const matrix_data_t r2x3_180[6] = { 5,4,3,2,1,0 };
const matrix_data_t r3x2_r90[6] = { 4,2,0,5,3,1 };
const matrix_data_t r3x2_l90[6] = { 1,3,5,0,2,4 };
const matrix_data_t r3x2_180[6] = { 5,4,3,2,1,0 };
const matrix_data_t r6x1_r90[6] = { 5,4,3,2,1,0 };
const matrix_data_t r6x1_l90[6] = { 0,1,2,3,4,5 };
const matrix_data_t r6x1_180[6] = { 5,4,3,2,1,0 };
/* sq3x3 tests */
rotate(90, sq3x3, sq3x3_copy, 3, 3); /* +90 */
assert(!test_cmp(sq3x3_copy, sq3x3_r90, 3, 3));
rotate(-90, sq3x3, sq3x3_copy, 3, 3); /* -90 */
assert(!test_cmp(sq3x3_copy, sq3x3_l90, 3, 3));
rotate(180, sq3x3, sq3x3_copy, 3, 3); /* 180 */
assert(!test_cmp(sq3x3_copy, sq3x3_180, 3, 3));
/* sq3x3 in-place rotations */
memcpy( sq3x3_copy, sq3x3, 3 * 3 * sizeof(matrix_data_t));
rotate_inplace(90, sq3x3_copy, 3);
assert(!test_cmp(sq3x3_copy, sq3x3_r90, 3, 3));
rotate_inplace(-90, sq3x3_copy, 3);
assert(!test_cmp(sq3x3_copy, sq3x3, 3, 3)); /* back to 0 orientation */
rotate_inplace(180, sq3x3_copy, 3);
assert(!test_cmp(sq3x3_copy, sq3x3_180, 3, 3));
rotate_inplace(-180, sq3x3_copy, 3);
assert(!test_cmp(sq3x3_copy, sq3x3, 3, 3));
rotate_inplace(180, (matrix_data_t*)sq3x3_2D, 3);/* 2D test */
assert(!test_cmp((matrix_data_t*)sq3x3_2D, sq3x3_180, 3, 3));
/* sq4x4 */
rotate(90, (matrix_data_t*)sq4x4, (matrix_data_t*)sq4x4_copy, 4, 4);
assert(!test_cmp((matrix_data_t*)sq4x4_copy, sq4x4_r90, 4, 4));
rotate(-90, (matrix_data_t*)sq4x4, (matrix_data_t*)sq4x4_copy, 4, 4);
assert(!test_cmp((matrix_data_t*)sq4x4_copy, sq4x4_l90, 4, 4));
rotate(180, (matrix_data_t*)sq4x4, (matrix_data_t*)sq4x4_copy, 4, 4);
assert(!test_cmp((matrix_data_t*)sq4x4_copy, sq4x4_180, 4, 4));
/* r6 as 1x6 */
rotate(90, r6, r6_copy, 1, 6);
assert(!test_cmp(r6_copy, r1x6_r90, 1, 6));
rotate(-90, r6, r6_copy, 1, 6);
assert(!test_cmp(r6_copy, r1x6_l90, 1, 6));
rotate(180, r6, r6_copy, 1, 6);
assert(!test_cmp(r6_copy, r1x6_180, 1, 6));
/* r6 as 2x3 */
rotate(90, r6, r6_copy, 2, 3);
assert(!test_cmp(r6_copy, r2x3_r90, 2, 3));
rotate(-90, r6, r6_copy, 2, 3);
assert(!test_cmp(r6_copy, r2x3_l90, 2, 3));
rotate(180, r6, r6_copy, 2, 3);
assert(!test_cmp(r6_copy, r2x3_180, 2, 3));
/* r6 as 3x2 */
rotate(90, r6, r6_copy, 3, 2);
assert(!test_cmp(r6_copy, r3x2_r90, 3, 2));
rotate(-90, r6, r6_copy, 3, 2);
assert(!test_cmp(r6_copy, r3x2_l90, 3, 2));
rotate(180, r6, r6_copy, 3, 2);
assert(!test_cmp(r6_copy, r3x2_180, 3, 2));
/* r6 as 6x1 */
rotate(90, r6, r6_copy, 6, 1);
assert(!test_cmp(r6_copy, r6x1_r90, 6, 1));
rotate(-90, r6, r6_copy, 6, 1);
assert(!test_cmp(r6_copy, r6x1_l90, 6, 1));
rotate(180, r6, r6_copy, 6, 1);
assert(!test_cmp(r6_copy, r6x1_180, 6, 1));
}
/* test comparison fn, return 0 on match else non zero */
int test_cmp(const matrix_data_t* lhs, const matrix_data_t* rhs, int rows, int cols) {
int r, c;
for (r = 0; r < rows; ++r) {
for (c = 0; c < cols; ++c) {
if ((lhs + r * cols)[c] != (rhs + r * cols)[c])
return -1;
}
}
return 0;
}
/*
Reverse values in place of each row in 2D matrix data[rows][cols] or in 1D pointer with logical rows/cols
[A B C] -> [C B A]
[D E F] [F E D]
*/
void reverse_rows(matrix_data_t* data, int rows, int cols) {
int r, c;
matrix_data_t temp;
matrix_data_t* pRow = NULL;
for (r = 0; r < rows; ++r) {
pRow = (data + r * cols);
for (c = 0; c < (int)(cols / 2); ++c) { /* explicit truncate */
temp = pRow[c];
pRow[c] = pRow[cols - 1 - c];
pRow[cols - 1 - c] = temp;
}
}
}
/*
Reverse values in place of each column in 2D matrix data[rows][cols] or in 1D pointer with logical rows/cols
[A B C] -> [D E F]
[D E F] [A B C]
*/
void reverse_cols(matrix_data_t* data, int rows, int cols) {
int r, c;
matrix_data_t temp;
matrix_data_t* pRowA = NULL;
matrix_data_t* pRowB = NULL;
for (c = 0; c < cols; ++c) {
for (r = 0; r < (int)(rows / 2); ++r) { /* explicit truncate */
pRowA = data + r * cols;
pRowB = data + cols * (rows - 1 - r);
temp = pRowA[c];
pRowA[c] = pRowB[c];
pRowB[c] = temp;
}
}
}
/* Transpose NxM matrix to MxN matrix in O(n) time */
void transpose(const matrix_data_t* src, matrix_data_t* dst, int N, int M) {
int i;
for (i = 0; i<N*M; ++i) dst[(i%M)*N + (i / M)] = src[i]; /* one-liner version */
/*
expanded version of one-liner: calculate XY based on array index, then convert that to YX array index
int i,j,x,y;
for (i = 0; i < N*M; ++i) {
x = i % M;
y = (int)(i / M);
j = x * N + y;
dst[j] = src[i];
}
*/
/*
nested for loop version
using ptr arithmetic to get proper row/column
this is really just dst[col][row]=src[row][col]
int r, c;
for (r = 0; r < rows; ++r) {
for (c = 0; c < cols; ++c) {
(dst + c * rows)[r] = (src + r * cols)[c];
}
}
*/
}
/*
Transpose NxN matrix in place
*/
void transpose_inplace(matrix_data_t* data, int N ) {
int r, c;
matrix_data_t temp;
for (r = 0; r < N; ++r) {
for (c = r; c < N; ++c) { /*start at column=row*/
/* using ptr arithmetic to get proper row/column */
/* this is really just
temp=dst[col][row];
dst[col][row]=src[row][col];
src[row][col]=temp;
*/
temp = (data + c * N)[r];
(data + c * N)[r] = (data + r * N)[c];
(data + r * N)[c] = temp;
}
}
}
/*
Rotate 1D or 2D src matrix to dst matrix in a direction (90,180,-90)
Precondition: src and dst are 2d matrices with dimensions src[rows][cols] and dst[cols][rows] or 1D pointers with logical rows/cols
*/
void rotate(int direction, const matrix_data_t* src, matrix_data_t* dst, int rows, int cols) {
switch (direction) {
case -90:
transpose(src, dst, rows, cols);
reverse_cols(dst, cols, rows);
break;
case 90:
transpose(src, dst, rows, cols);
reverse_rows(dst, cols, rows);
break;
case 180:
case -180:
/* bit copy to dst, use in-place reversals */
memcpy(dst, src, rows*cols*sizeof(matrix_data_t));
reverse_cols(dst, cols, rows);
reverse_rows(dst, cols, rows);
break;
}
}
/*
Rotate array in a direction.
Array must be NxN 2D or 1D array with logical rows/cols
Direction can be (90,180,-90,-180)
*/
void rotate_inplace( int direction, matrix_data_t* data, int n) {
switch (direction) {
case -90:
transpose_inplace(data, n);
reverse_cols(data, n, n);
break;
case 90:
transpose_inplace(data, n);
reverse_rows(data, n, n);
break;
case 180:
case -180:
reverse_cols(data, n, n);
reverse_rows(data, n, n);
break;
}
}
`
ruby方式:.transpose。地图&:反向
