如何旋转二维数组?

小开

最佳答案

这是c#的

int[,] array = new int[4,4] {
{ 1,2,3,4 },
{ 5,6,7,8 },
{ 9,0,1,2 },
{ 3,4,5,6 }
};


int[,] rotated = RotateMatrix(array, 4);


static int[,] RotateMatrix(int[,] matrix, int n) {
int[,] ret = new int[n, n];


for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
ret[i, j] = matrix[n - j - 1, i];
}
}


return ret;
}

小开

下面是我的Ruby版本(注意，值显示的不一样，但它仍然按照描述旋转)。

def rotate(matrix)
result = []
4.times { |x|
result[x] = []
4.times { |y|
result[x][y] = matrix[y][3 - x]
}
}


result
end


matrix = []
matrix[0] = [1,2,3,4]
matrix[1] = [5,6,7,8]
matrix[2] = [9,0,1,2]
matrix[3] = [3,4,5,6]


def print_matrix(matrix)
4.times { |y|
4.times { |x|
print "#{matrix[x][y]} "
}
puts ""
}
end


print_matrix(matrix)
puts ""
print_matrix(rotate(matrix))

输出:

小开

尼克的答案也适用于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)的中心从左上角移动到右上角。你只是简单地从一个转置到另一个。

小开

一些人已经举了一些例子，其中涉及到创建一个新数组。

还有一些需要考虑的事情:

(a)不实际移动数据，只需以不同的方式遍历“旋转”的数组。

(b)就地轮换可能有点棘手。您需要一点空白的地方(大概相当于一行或一列的大小)。有一篇古老的ACM论文是关于进行原地转置(http://doi.acm.org/10.1145/355719.355729)的，但他们的示例代码是讨厌的goto负载的FORTRAN。

附录:

http://doi.acm.org/10.1145/355611.355612是另一个，据说更好的，就地转置算法。

小开

正如我在上一篇文章中所说的，这里有一些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。对构造函数稍加更改，创建一个新数组并将值复制到该数组中，就可以将其整理出来。

小开

下面是一个原地旋转的数组，而不是使用一个全新的数组来保存结果。我已经停止了数组的初始化和输出。这只适用于正方形数组，但它们可以是任何大小。内存开销等于数组中一个元素的大小，因此您可以对任意大的数组进行旋转。

int a[4][4];
int n = 4;
int tmp;
for (int i = 0; i < n / 2; i++)
{
for (int j = i; j < n - i - 1; j++)
{
tmp             = a[i][j];
a[i][j]         = a[j][n-i-1];
a[j][n-i-1]     = a[n-i-1][n-j-1];
a[n-i-1][n-j-1] = a[n-j-1][i];
a[n-j-1][i]     = tmp;
}
}

小开

哦，伙计。我一直认为这是一个“我很无聊，我能思考什么”的谜题。我想出了我的原地换位码，但到了这里发现你的和我的几乎一模一样……啊,好。这里是Ruby版本。

require 'pp'
n = 10
a = []
n.times { a << (1..n).to_a }


pp a


0.upto(n/2-1) do |i|
i.upto(n-i-2) do |j|
tmp             = a[i][j]
a[i][j]         = a[n-j-1][i]
a[n-j-1][i]     = a[n-i-1][n-j-1]
a[n-i-1][n-j-1] = a[j][n-i-1]
a[j][n-i-1]     = tmp
end
end


pp a

小开

虽然旋转数据可能是必要的(也许是为了更新物理存储的表示)，但在数组访问上添加一层间接层(也许是一个接口)会变得更简单，可能更性能:

interface IReadableMatrix
{
int GetValue(int x, int y);
}

如果你的Matrix已经实现了这个接口，那么它可以通过装饰类像这样旋转:

class RotatedMatrix : IReadableMatrix
{
private readonly IReadableMatrix _baseMatrix;


public RotatedMatrix(IReadableMatrix baseMatrix)
{
_baseMatrix = baseMatrix;
}


int GetValue(int x, int y)
{
// transpose x and y dimensions
return _baseMatrix(y, x);
}
}

旋转+90/-90/180度，水平/垂直翻转和缩放都可以以这种方式实现。

性能需要在特定的场景中进行测量。然而，O(n²)操作现在已经被O(1)调用所取代。它是一个虚方法调用，是比直接数组访问慢，因此它取决于旋转后使用旋转数组的频率。如果只使用一次，那么这种方法肯定会成功。如果将其旋转，然后在长时间运行的系统中使用数天，那么就地旋转可能会执行得更好。这也取决于你是否能接受预付费用。

与所有性能问题一样，测量，测量，测量!

小开

Python:

rotated = list(zip(*original[::-1]))

和逆时针方向:

rotated_ccw = list(zip(*original))[::-1]

这是如何工作的:

zip(*original)将交换2d数组的轴，将对应的项从列表堆叠到新的列表中。(*运营商告诉函数将包含的列表分布到参数中)

>>> list(zip(*[[1,2,3],[4,5,6],[7,8,9]]))
[[1,4,7],[2,5,8],[3,6,9]]

[::-1]语句反转数组元素(请参阅长片或这个问题):

>>> [[1,2,3],[4,5,6],[7,8,9]][::-1]
[[7,8,9],[4,5,6],[1,2,3]]

最后，将两者结合就得到了旋转变换。

改变[::-1]的位置将颠倒矩阵中不同层次的列表。

小开

#include <iostream>
#include <iomanip>


using namespace std;
const int SIZE=3;
void print(int a[][SIZE],int);
void rotate(int a[][SIZE],int);


void main()
{
int a[SIZE][SIZE]=\{\{11,22,33},{44,55,66},{77,88,99}};
cout<<"the array befor rotate\n";


print(a,SIZE);
rotate( a,SIZE);
cout<<"the array after rotate\n";
print(a,SIZE);
cout<<endl;


}


void print(int a[][SIZE],int SIZE)
{
int i,j;
for(i=0;i<SIZE;i++)
for(j=0;j<SIZE;j++)
cout<<a[i][j]<<setw(4);
}


void rotate(int a[][SIZE],int SIZE)
{
int temp[3][3],i,j;
for(i=0;i<SIZE;i++)
for(j=0;j<SIZE/2.5;j++)
{
temp[i][j]= a[i][j];
a[i][j]= a[j][SIZE-i-1] ;
a[j][SIZE-i-1] =temp[i][j];


}
}

小开

short normal[4][4] = \{\{8,4,7,5},{3,4,5,7},{9,5,5,6},{3,3,3,3}};


short rotated[4][4];


for (int r = 0; r < 4; ++r)
{
for (int c = 0; c < 4; ++c)
{
rotated[r][c] = normal[c][3-r];
}
}

简单的c++方法，尽管在大数组中会有很大的内存开销。

小开

这是Java中的一个更好的版本:我已经为一个具有不同宽度和高度的矩阵制作了它

H是旋转后矩阵的高度
W是旋转后矩阵的宽度

,

public int[][] rotateMatrixRight(int[][] matrix)
{
/* W and H are already swapped */
int w = matrix.length;
int h = matrix[0].length;
int[][] ret = new int[h][w];
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
ret[i][j] = matrix[w - j - 1][i];
}
}
return ret;
}




public int[][] rotateMatrixLeft(int[][] matrix)
{
/* W and H are already swapped */
int w = matrix.length;
int h = matrix[0].length;
int[][] ret = new int[h][w];
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
ret[i][j] = matrix[j][h - i - 1];
}
}
return ret;
}

此代码基于Nick Berardi的帖子。

小开

PHP:

<?php
$a = array(array(1,2,3,4),array(5,6,7,8),array(9,0,1,2),array(3,4,5,6));
$b = array(); //result


while(count($a)>0)
{
$b[count($a[0])-1][] = array_shift($a[0]);
if (count($a[0])==0)
{
array_shift($a);
}
}

从PHP5.6开始，数组转位可以通过一个狡猾的array_map()调用来执行。换句话说，列被转换为行。

代码(演示):

$array = [
[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 0, 1, 2],
[3, 4, 5, 6]
];
$transposed = array_map(null, ...$array);

美元转置:

[
[1, 5, 9, 3],
[2, 6, 0, 4],
[3, 7, 1, 5],
[4, 8, 2, 6]
]

小开

当前所有的解决方案都有O(n^2)开销作为临时空间(这不包括那些肮脏的OOP骗子!)这里有一个内存占用为O(1)的解决方案，将矩阵原地右转90度。该死的延展性，这玩意儿跑得很快!

#include <algorithm>
#include <cstddef>


// Rotates an NxN matrix of type T 90 degrees to the right.
template <typename T, size_t N>
void rotate_matrix(T (&matrix)[N][N])
{
for(size_t i = 0; i < N; ++i)
for(size_t j = 0; j <= (N-i); ++j)
std::swap(matrix[i][j], matrix[j][i]);
}

免责声明:我实际上并没有测试这个。让我们玩打虫游戏吧!

小开

ruby方式:.transpose.map &:reverse

小开

O(n²)时间和O(1)空间算法(没有任何变通和恶作剧的东西!)

旋转+90:

转置
反转每行

旋转-90:

方法一:

转置
反转每一列

方法二:

反转每行
转置

旋转180度:

方法1:旋转+90两次

方法2:反转每一行，然后反转每一列(转置)

旋转-180度:

方法1:旋转-90两次

方法2:反转每一列，然后反转每一行

方法3:当它们相同时旋转+180

小开

For i:= 0 to X do 对于j:= 0到X做 [j][i]:= graphic2[X-i][j]

X是图形所在数组的大小。

小开

这是一个空间旋转方法，由java编写，只适用于正方形。对于非正方形的2d数组，无论如何都必须创建新数组。

private void rotateInSpace(int[][] arr) {
int z = arr.length;
for (int i = 0; i < z / 2; i++) {
for (int j = 0; j < (z / 2 + z % 2); j++) {
int x = i, y = j;
int temp = arr[x][y];
for (int k = 0; k < 4; k++) {
int temptemp = arr[y][z - x - 1];
arr[y][z - x - 1] = temp;
temp = temptemp;


int tempX = y;
y = z - x - 1;
x = tempX;
}
}
}
}

通过创建新数组旋转任何大小的2d数组的代码:

private int[][] rotate(int[][] arr) {
int width = arr[0].length;
int depth = arr.length;
int[][] re = new int[width][depth];
for (int i = 0; i < depth; i++) {
for (int j = 0; j < width; j++) {
re[j][depth - i - 1] = arr[i][j];
}
}
return re;
}

小开

这是我的实现，在C, O(1)内存复杂度，原地旋转，顺时针90度:

#include <stdio.h>


#define M_SIZE 5


static void initMatrix();
static void printMatrix();
static void rotateMatrix();


static int m[M_SIZE][M_SIZE];


int main(void){
initMatrix();
printMatrix();
rotateMatrix();
printMatrix();


return 0;
}


static void initMatrix(){
int i, j;


for(i = 0; i < M_SIZE; i++){
for(j = 0; j < M_SIZE; j++){
m[i][j] = M_SIZE*i + j + 1;
}
}
}


static void printMatrix(){
int i, j;


printf("Matrix\n");
for(i = 0; i < M_SIZE; i++){
for(j = 0; j < M_SIZE; j++){
printf("%02d ", m[i][j]);
}
printf("\n");
}
printf("\n");
}


static void rotateMatrix(){
int r, c;


for(r = 0; r < M_SIZE/2; r++){
for(c = r; c < M_SIZE - r - 1; c++){
int tmp = m[r][c];


m[r][c] = m[M_SIZE - c - 1][r];
m[M_SIZE - c - 1][r] = m[M_SIZE - r - 1][M_SIZE - c - 1];
m[M_SIZE - r - 1][M_SIZE - c - 1] = m[c][M_SIZE - r - 1];
m[c][M_SIZE - r - 1] = tmp;
}
}
}

小开

#转置是Ruby的Array类的标准方法，因此:

% irb
irb(main):001:0> m = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 0, 1, 2], [3, 4, 5, 6]]
=> [[1, 2, 3, 4], [5, 6, 7, 8], [9, 0, 1, 2], [3, 4, 5, 6]]
irb(main):002:0> m.reverse.transpose
=> [[3, 9, 5, 1], [4, 0, 6, 2], [5, 1, 7, 3], [6, 2, 8, 4]]

实现是一个用c写的n^2转置函数，你可以在这里看到: http://www.ruby-doc.org/core-1.9.3/Array.html#method-i-transpose 在“转置”旁边选择“点击切换源”

我记得比O(n^2)的解更好，但只适用于特殊构造的矩阵(如稀疏矩阵)

小开

C代码的矩阵旋转90度顺时针在任何M*N矩阵的地方

void rotateInPlace(int * arr[size][size], int row, int column){
int i, j;
int temp = row>column?row:column;
int flipTill = row < column ? row : column;
for(i=0;i<flipTill;i++){
for(j=0;j<i;j++){
swapArrayElements(arr, i, j);
}
}


temp = j+1;


for(i = row>column?i:0; i<row; i++){
for(j=row<column?temp:0; j<column; j++){
swapArrayElements(arr, i, j);
}
}


for(i=0;i<column;i++){
for(j=0;j<row/2;j++){
temp = arr[i][j];
arr[i][j] = arr[i][row-j-1];
arr[i][row-j-1] = temp;
}
}
}

小开

这是我对矩阵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;
}

小开

O(1)内存算法:

旋转最外层的数据，然后你可以得到以下结果:
```
[3][9][5][1]
[4][6][7][2]
[5][0][1][3]
[6][2][8][4]
```

To do this rotation, we know

    dest[j][n-1-i] = src[i][j]

< p >观察如下: A (0,0) -> A (0,3) A (0,3) -> A (3,3) A (3,3) -> A (3,0) A (3,0) -> A (0,0)

因此它是一个圆，你可以在一个循环中旋转N个元素。做这个N-1循环，然后你可以旋转最外层的元素。

对于2X2，内部也是一样的问题。

因此，我们可以得出如下结论:

function rotate(array, N)
{
Rotate outer-most data
rotate a new array with N-2 or you can do the similar action following step1
}

小开

下面是Java版本:

public static void rightRotate(int[][] matrix, int n) {
for (int layer = 0; layer < n / 2; layer++) {
int first = layer;
int last = n - 1 - first;
for (int i = first; i < last; i++) {
int offset = i - first;
int temp = matrix[first][i];
matrix[first][i] = matrix[last-offset][first];
matrix[last-offset][first] = matrix[last][last-offset];
matrix[last][last-offset] = matrix[i][last];
matrix[i][last] = temp;
}
}
}

该方法首先旋转最外层，然后按顺序移动到内层。

小开

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中的就地实现

void rotateRight(int matrix[][SIZE], int length) {


int layer = 0;


for (int layer = 0; layer < length / 2; ++layer) {


int first = layer;
int last = length - 1 - layer;


for (int i = first; i < last; ++i) {


int topline = matrix[first][i];
int rightcol = matrix[i][last];
int bottomline = matrix[last][length - layer - 1 - i];
int leftcol = matrix[length - layer - 1 - i][first];


matrix[first][i] = leftcol;
matrix[i][last] = topline;
matrix[last][length - layer - 1 - i] = rightcol;
matrix[length - layer - 1 - i][first] = bottomline;
}
}
}

小开

在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;
}

小开

这里有大量的好代码，但我只是想以几何形式展示，这样你就能更好地理解代码逻辑。以下是我的处理方法。

首先，不要把这和换位相混淆，换位是很容易的。

基本的想法是把它当作层，我们一次旋转一个层。

假设我们有一辆4x4

1   2   3   4
5   6   7   8
9   10  11  12
13  14  15  16

当我们顺时针旋转90度，我们得到

13  9   5   1
14  10  6   2
15  11  7   3
16  12  8   4

我们来分解它，首先旋转这四个角

1           4




13          16

然后我们旋转下面这个有点歪斜的菱形

然后是第二个斜菱形

这就搞定了外缘基本上我们一次做一个壳层直到

最后是中间的方块(如果是奇数则是最后一个不动的元素)

6   7
10  11

现在我们来算出每一层的指标，假设我们总是在最外层工作，我们正在做

[0,0] -> [0,n-1], [0,n-1] -> [n-1,n-1], [n-1,n-1] -> [n-1,0], and [n-1,0] -> [0,0]
[0,1] -> [1,n-1], [1,n-2] -> [n-1,n-2], [n-1,n-2] -> [n-2,0], and [n-2,0] -> [0,1]
[0,2] -> [2,n-2], [2,n-2] -> [n-1,n-3], [n-1,n-3] -> [n-3,0], and [n-3,0] -> [0,2]

等等直到边

所以总的来说模式是

[0,i] -> [i,n-i], [i,n-i] -> [n-1,n-(i+1)], [n-1,n-(i+1)] -> [n-(i+1),0], and [n-(i+1),0] to [0,i]

小开

原地旋转不可能比O(n²)更快，原因是如果我们想旋转矩阵，我们必须至少一次触及所有n²元素，无论你实现什么算法。

小开

时间- O(N)，空间- O(1)

public void rotate(int[][] matrix) {
int n = matrix.length;
for (int i = 0; i < n / 2; i++) {
int last = n - 1 - i;
for (int j = i; j < last; j++) {
int top = matrix[i][j];
matrix[i][j] = matrix[last - j][i];
matrix[last - j][i] = matrix[last][last - j];
matrix[last][last - j] = matrix[j][last];
matrix[j][last] = top;
}
}
}

小开

下面是PHP的递归方法:

$m = array();
$m[0] = array('a', 'b', 'c');
$m[1] = array('d', 'e', 'f');
$m[2] = array('g', 'h', 'i');
$newMatrix = array();


function rotateMatrix($m, $i = 0, &$newMatrix)
{
foreach ($m as $chunk) {
$newChunk[] = $chunk[$i];
}
$newMatrix[] = array_reverse($newChunk);
$i++;


if ($i < count($m)) {
rotateMatrix($m, $i, $newMatrix);
}
}


rotateMatrix($m, 0, $newMatrix);
echo '<pre>';
var_dump($newMatrix);
echo '<pre>';

小开

我的旋转版本:

void rotate_matrix(int *matrix, int size)
{


int result[size*size];


for (int i = 0; i < size; ++i)
for (int j = 0; j < size; ++j)
result[(size - 1 - i) + j*size] = matrix[i*size+j];


for (int i = 0; i < size*size; ++i)
matrix[i] = result[i];
}

在其中，我们将最后一列改为第一行，以此类推。这可能不是最理想的，但对于理解来说是清楚的。

小开

为新手程序员，在纯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;
}

小开

#!/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]]

小开

PHP:

array_unshift($array, null);
$array = call_user_func_array("array_map", $array);

如果你需要旋转矩形二维阵列90度，在上面的代码之前或之后添加以下一行(取决于你需要的旋转方向):

$array = array_reverse($array);

小开

从线性的角度来看，考虑以下矩阵:

    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'的作用分别为:< / p >

      7 4 1          3 6 9
A'B = 8 5 2    BA' = 2 5 8
9 6 3          1 4 7

这对任何n × n矩阵都是可展开的。在代码中快速应用这个概念:

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);
}
}
}

小开

已经有很多答案了，我发现两个声称O(1)时间复杂度。真正的 O(1)算法是保持数组存储不变，并改变索引其元素的方式。这里的目标是不消耗额外的内存，也不需要额外的时间来迭代数据。

旋转90度，-90度和180度是简单的转换，只要你知道你的2D数组中有多少行和列就可以执行;要将任何向量旋转90度，交换轴并与Y轴相反。对于-90度，交换轴和X轴。对于180度，两个坐标轴都是负的，不交换。

进一步的转换是可能的，例如通过独立地否定轴来水平和/或垂直地镜像。

这可以通过访问器方法来实现。下面的例子是JavaScript函数，但是这些概念同样适用于所有语言。

 // Get an array element in column/row order
var getArray2d = function(a, x, y) {
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.length; i++) {
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);

这段代码假设有一个嵌套数组的数组，其中每个内部数组都是一行。

该方法允许您读取(或写入)元素(甚至是随机顺序)，就像数组已经旋转或转换一样。现在只要选择正确的函数来调用，可能是通过引用，然后就可以了!

这个概念可以扩展为通过访问器方法附加地(非破坏性地)应用转换。包括任意角度旋转和缩放。

小开

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;
}

小开

c#代码将[n,m] 2D数组向右旋转90度

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;


namespace MatrixProject
{
// mattrix class


class Matrix{
private int rows;
private int cols;
private int[,] matrix;


public Matrix(int n){
this.rows = n;
this.cols = n;
this.matrix = new int[this.rows,this.cols];


}


public Matrix(int n,int m){
this.rows = n;
this.cols = m;


this.matrix = new int[this.rows,this.cols];
}


public void Show()
{
for (var i = 0; i < this.rows; i++)
{
for (var j = 0; j < this.cols; j++) {
Console.Write("{0,3}", this.matrix[i, j]);
}
Console.WriteLine();
}
}


public void ReadElements()
{
for (var i = 0; i < this.rows; i++)
for (var j = 0; j < this.cols; j++)
{
Console.Write("element[{0},{1}]=",i,j);
this.matrix[i, j] = Convert.ToInt32(Console.ReadLine());
}
}




// rotate [n,m] 2D array by 90 deg right
public void Rotate90DegRight()
{


// create a mirror of current matrix
int[,] mirror = this.matrix;


// create a new matrix
this.matrix = new int[this.cols, this.rows];


for (int i = 0; i < this.rows; i++)
{
for (int j = 0; j < this.cols; j++)
{
this.matrix[j, this.rows - i - 1] = mirror[i, j];
}
}


// replace cols count with rows count
int tmp = this.rows;
this.rows = this.cols;
this.cols = tmp;
}
}


class Program
{
static void Main(string[] args)
{
Matrix myMatrix = new Matrix(3,4);
Console.WriteLine("Enter matrix elements:");
myMatrix.ReadElements();
Console.WriteLine("Matrix elements are:");
myMatrix.Show();
myMatrix.Rotate90DegRight();
Console.WriteLine("Matrix rotated at 90 deg are:");
myMatrix.Show();
Console.ReadLine();
}
}
}

结果:

    Enter matrix elements:
element[0,0]=1
element[0,1]=2
element[0,2]=3
element[0,3]=4
element[1,0]=5
element[1,1]=6
element[1,2]=7
element[1,3]=8
element[2,0]=9
element[2,1]=10
element[2,2]=11
element[2,3]=12
Matrix elements are:
1  2  3  4
5  6  7  8
9 10 11 12
Matrix rotated at 90 deg are:
9  5  1
10  6  2
11  7  3
12  8  4

小开

/* 90-degree clockwise:
temp_array         = left_col
left_col           = bottom_row
bottom_row         = reverse(right_col)
reverse(right_col) = reverse(top_row)
reverse(top_row)   = temp_array
*/
void RotateClockwise90(int ** arr, int lo, int hi) {


if (lo >= hi)
return;


for (int i=lo; i<hi; i++) {
int j = lo+hi-i;
int temp   = arr[i][lo];
arr[i][lo] = arr[hi][i];
arr[hi][i] = arr[j][hi];
arr[j][hi] = arr[lo][j];
arr[lo][j] = temp;
}


RotateClockwise90(arr, lo+1, hi-1);
}

小开

在原地顺时针90度旋转使用矢量矢量..

 #include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
//Rotate a Matrix by 90 degrees
void rotateMatrix(vector<vector<int> > &matrix){
int n=matrix.size();
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
swap(matrix[i][j],matrix[j][i]);
}
}
for(int i=0;i<n;i++){
reverse(matrix[i].begin(),matrix[i].end());
}
}


int main(){


int n;
cout<<"enter the size of the matrix:"<<endl;
while (cin >> n) {
vector< vector<int> > m;
cout<<"enter the elements"<<endl;
for (int i = 0; i < n; i++) {
m.push_back(vector<int>(n));
for (int j = 0; j < n; j++)
scanf("%d", &m[i][j]);
}
cout<<"the rotated matrix is:"<<endl;
rotateMatrix(m);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
cout << m[i][j] << ' ';
cout << endl;
}
}
return 0;
}

小开

Javascript解决NxN矩阵与运行时O(N^2)和内存O(1)

  function rotate90(matrix){
var length = matrix.length
for(var row = 0; row < (length / 2); row++){
for(var col = row; col < ( length - 1 - row); col++){
var tmpVal = matrix[row][col];
for(var i = 0; i < 4; i++){
var rowSwap = col;
var colSwap = (length - 1) - row;
var poppedVal = matrix[rowSwap][colSwap];
matrix[rowSwap][colSwap] = tmpVal;
tmpVal = poppedVal;
col = colSwap;
row = rowSwap;
}
}
}
}

小开

这是一个如今被高估的面试问题。

我的建议是:不要让面试官用他们关于解决这个问题的疯狂建议把你弄糊涂了。使用白板绘制输入数组的索引，然后绘制输出数组的索引。旋转前后的列分度示例如下:

30 --> 00
20 --> 01
10 --> 02
00 --> 03


31 --> 10
21 --> 11
11 --> 12
01 --> 13

注意旋转后的数字模式。

下面提供了一个简洁的Java解决方案。经过测试，它是有效的:

 Input:
M A C P
B N L D
Y E T S
I W R Z


Output:
I Y B M
W E N A
R T L C
Z S D P


/**
* (c) @author "G A N MOHIM"
* Oct 3, 2015
* RotateArrayNintyDegree.java
*/
package rotatearray;


public class RotateArrayNintyDegree {


public char[][] rotateArrayNinetyDegree(char[][] input) {
int k; // k is used to generate index for output array


char[][] output = new char[input.length] [input[0].length];


for (int i = 0; i < input.length; i++) {
k = 0;
for (int j = input.length-1; j >= 0; j--) {
output[i][k] = input[j][i]; // note how i is used as column index, and j as row
k++;
}
}


return output;
}


public void printArray(char[][] charArray) {
for (int i = 0; i < charArray.length; i++) {
for (int j = 0; j < charArray[0].length; j++) {
System.out.print(charArray[i][j] + " ");
}
System.out.println();
}




}


public static void main(String[] args) {
char[][] input =
{ {'M', 'A', 'C', 'P'},
{'B', 'N', 'L', 'D'},
{'Y', 'E', 'T', 'S'},
{'I', 'W', 'R', 'Z'}
};


char[][] output = new char[input.length] [input[0].length];


RotateArrayNintyDegree rotationObj = new RotateArrayNintyDegree();
rotationObj.printArray(input);


System.out.println("\n");
output = rotationObj.rotateArrayNinetyDegree(input);
rotationObj.printArray(output);


}


}

小开

你可以在简单3步中这样做:

假设我们有一个矩阵

   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();
}
}
}

输出:

小开

下面是Java语言:

public static void rotateInPlace(int[][] m) {
for(int layer = 0; layer < m.length/2; layer++){
int first = layer;
int last = m.length - 1 - first;
for(int i = first; i < last; i ++){
int offset = i - first;
int top = m[first][i];
m[first][i] = m[last - offset][first];
m[last - offset][first] = m[last][last - offset];
m[last][last - offset] = m[i][last];
m[i][last] = top;
}
}
}

小开

我想再补充一点细节。在这个答案中，关键概念被重复，节奏缓慢，故意重复。这里提供的解决方案在语法上不是最紧凑的，但是，它是为那些希望了解什么是矩阵旋转及其实现的人设计的。

首先，什么是矩阵?为了回答这个问题，矩阵就是一个宽度和高度相同的网格。注意，矩阵的宽度和高度可以不同，但为了简单起见，本教程只考虑宽度和高度相等的矩阵(方阵)。是的，矩阵是matrix的复数。

例如:2×2, 3×3或5×5。或者更通俗地说，N×N。2×2矩阵将有4个方框，因为2×2=4。一个5×5矩阵将有25个正方形，因为5×5=25。每个方格称为一个元素或项。在下面的图表中，我们将用句点(.)表示每个元素:

2×2的矩阵

. .
. .

3×3矩阵

. . .
. . .
. . .

4×4矩阵

. . . .
. . . .
. . . .
. . . .

旋转一个矩阵意味着什么?让我们取一个2×2矩阵，在每个元素中放入一些数字，这样就可以观察到旋转:

0 1
2 3

将其旋转90度得到:

2 0
3 1

我们把整个矩阵向右转一次就像转汽车的方向盘一样。考虑将矩阵“倾斜”到右侧可能会有所帮助。我们想用Python写一个函数，取一个矩阵并向右旋转一次。函数签名将是:

def rotate(matrix):
# Algorithm goes here.

矩阵将使用一个二维数组定义:

matrix = [
[0,1],
[2,3]
]

因此，第一个索引位置访问行。第二个索引位置访问列:

matrix[row][column]

我们将定义一个效用函数来打印一个矩阵。

def print_matrix(matrix):
for row in matrix:
print row

旋转矩阵的一种方法是一次旋转一层。但是什么是层呢?想象一个洋葱。就像洋葱的一层一层，随着每一层的移除，我们向中心移动。另一个类比是俄罗斯娃娃或传递包裹的游戏。

矩阵的宽度和高度决定了该矩阵的层数。让我们为每一层使用不同的符号:

2×2矩阵有1层

. .
. .

3×3矩阵有两层

. . .
. x .
. . .

4×4矩阵有两层

. . . .
. x x .
. x x .
. . . .

5×5矩阵有3层

. . . . .
. x x x .
. x O x .
. x x x .
. . . . .

6×6矩阵有3层

. . . . . .
. x x x x .
. x O O x .
. x O O x .
. x x x x .
. . . . . .

7×7矩阵有4层

. . . . . . .
. x x x x x .
. x O O O x .
. x O - O x .
. x O O O x .
. x x x x x .
. . . . . . .

你可能会注意到，矩阵的宽度和高度增加一，并不总是增加层数。以上述矩阵为例，将层数和维度制成表格，我们可以看到层数每增加两个宽度和高度就会增加一次:

+-----+--------+
| N×N | Layers |
+-----+--------+
| 1×1 |      1 |
| 2×2 |      1 |
| 3×3 |      2 |
| 4×4 |      2 |
| 5×5 |      3 |
| 6×6 |      3 |
| 7×7 |      4 |
+-----+--------+

然而，并不是所有的层都需要旋转。1×1矩阵在旋转前后是相同的。无论整个矩阵有多大，中心1×1层在旋转前后总是相同的:

+-----+--------+------------------+
| N×N | Layers | Rotatable Layers |
+-----+--------+------------------+
| 1×1 |      1 |                0 |
| 2×2 |      1 |                1 |
| 3×3 |      2 |                1 |
| 4×4 |      2 |                2 |
| 5×5 |      3 |                2 |
| 6×6 |      3 |                3 |
| 7×7 |      4 |                3 |
+-----+--------+------------------+

给定N×N矩阵，我们如何以编程方式确定我们需要旋转的层数?如果我们将宽度或高度除以2，忽略余数，我们会得到以下结果。

+-----+--------+------------------+---------+
| N×N | Layers | Rotatable Layers |   N/2   |
+-----+--------+------------------+---------+
| 1×1 |      1 |                0 | 1/2 = 0 |
| 2×2 |      1 |                1 | 2/2 = 1 |
| 3×3 |      2 |                1 | 3/2 = 1 |
| 4×4 |      2 |                2 | 4/2 = 2 |
| 5×5 |      3 |                2 | 5/2 = 2 |
| 6×6 |      3 |                3 | 6/2 = 3 |
| 7×7 |      4 |                3 | 7/2 = 3 |
+-----+--------+------------------+---------+

注意N/2是如何匹配需要旋转的层数的?有时可旋转层数比矩阵的总层数少一层。当最内层只由一个元素(即1×1矩阵)形成时，就会发生这种情况，因此不需要旋转。它只是被忽略了。

毫无疑问，我们在函数中需要这个信息来旋转一个矩阵，所以让我们现在添加它:

def rotate(matrix):
size = len(matrix)
# Rotatable layers only.
layer_count = size / 2

现在我们知道什么是层，以及如何确定实际需要旋转的层数，我们如何隔离单个层以便我们可以旋转它?首先，我们检查一个矩阵，从最外层，向内，到最内层。5×5矩阵总共有三层，其中两层需要旋转:

. . . . .
. x x x .
. x O x .
. x x x .
. . . . .

让我们先看看列。定义最外层的列的位置，假设我们从0开始计数，是0和4:

+--------+-----------+
| Column | 0 1 2 3 4 |
+--------+-----------+
|        | . . . . . |
|        | . x x x . |
|        | . x O x . |
|        | . x x x . |
|        | . . . . . |
+--------+-----------+

0和4也是最外层的行位置。

+-----+-----------+
| Row |           |
+-----+-----------+
|   0 | . . . . . |
|   1 | . x x x . |
|   2 | . x O x . |
|   3 | . x x x . |
|   4 | . . . . . |
+-----+-----------+

这将总是这样，因为宽度和高度是相同的。因此，我们可以用两个值(而不是四个)定义一个层的列和行位置。

向内移动到第二层，列的位置为1和3。是的，你猜对了，对于行也是一样的。当向内移动到下一层时，我们必须同时增加和减少行和列的位置，理解这一点很重要。

+-----------+---------+---------+---------+
|   Layer   |  Rows   | Columns | Rotate? |
+-----------+---------+---------+---------+
| Outermost | 0 and 4 | 0 and 4 | Yes     |
| Inner     | 1 and 3 | 1 and 3 | Yes     |
| Innermost | 2       | 2       | No      |
+-----------+---------+---------+---------+

因此，为了检查每一层，我们需要一个循环，其中有递增和递减计数器，表示从最外层开始向内移动。我们称之为“层循环”。

def rotate(matrix):
size = len(matrix)
layer_count = size / 2


for layer in range(0, layer_count):
first = layer
last = size - first - 1
print 'Layer %d: first: %d, last: %d' % (layer, first, last)


# 5x5 matrix
matrix = [
[ 0, 1, 2, 3, 4],
[ 5, 6, 6, 8, 9],
[10,11,12,13,14],
[15,16,17,18,19],
[20,21,22,23,24]
]


rotate(matrix)

上面的代码循环遍历需要旋转的任何层的(行和列)位置。

Layer 0: first: 0, last: 4
Layer 1: first: 1, last: 3

现在我们有了一个循环，提供了每一层的行和列的位置。变量first和last确定了第一行和最后一列的索引位置。回到行表和列表:

+--------+-----------+
| Column | 0 1 2 3 4 |
+--------+-----------+
|        | . . . . . |
|        | . x x x . |
|        | . x O x . |
|        | . x x x . |
|        | . . . . . |
+--------+-----------+


+-----+-----------+
| Row |           |
+-----+-----------+
|   0 | . . . . . |
|   1 | . x x x . |
|   2 | . x O x . |
|   3 | . x x x . |
|   4 | . . . . . |
+-----+-----------+

所以我们可以在矩阵的层中导航。现在我们需要一种在层内导航的方法，这样我们就可以在该层周围移动元素。注意，元素从不从一个层“跳转”到另一个层，但它们确实在各自的层内移动。

旋转图层中的每个元素将旋转整个图层。旋转矩阵中的所有层将旋转整个矩阵。这句话很重要，所以在继续读下去之前请尽量理解它。

现在，我们需要一种实际移动元素的方法，即旋转每个元素，然后是层，最终是矩阵。为了简单起见，我们将恢复到一个3x3矩阵-它有一个可旋转的层。

0 1 2
3 4 5
6 7 8

我们的层循环提供了第一个和最后一个列的索引，以及第一个和最后一个行:

+-----+-------+
| Col | 0 1 2 |
+-----+-------+
|     | 0 1 2 |
|     | 3 4 5 |
|     | 6 7 8 |
+-----+-------+


+-----+-------+
| Row |       |
+-----+-------+
|   0 | 0 1 2 |
|   1 | 3 4 5 |
|   2 | 6 7 8 |
+-----+-------+

因为我们的矩阵总是方阵，所以我们只需要两个变量first和last，因为行和列的索引位置是相同的。

def rotate(matrix):
size = len(matrix)
layer_count = size / 2


# Our layer loop i=0, i=1, i=2
for layer in range(0, layer_count):


first = layer
last = size - first - 1
        

# We want to move within a layer here.

第一个和最后一个变量可以很容易地用于引用矩阵的四个角。这是因为角本身可以使用first和last的各种排列来定义(这些变量没有减法、加法或偏移量):

+---------------+-------------------+-------------+
| Corner        | Position          | 3x3 Values  |
+---------------+-------------------+-------------+
| top left      | (first, first)    | (0,0)       |
| top right     | (first, last)     | (0,2)       |
| bottom right  | (last, last)      | (2,2)       |
| bottom left   | (last, first)     | (2,0)       |
+---------------+-------------------+-------------+

出于这个原因，我们从外层的四个角开始旋转——我们先旋转它们。让我们用*突出显示它们。

* 1 *
3 4 5
* 7 *

我们希望将每个*与它右边的*交换。因此，让我们继续打印出仅使用first和last的各种排列定义的角:

def rotate(matrix):
size = len(matrix)
layer_count = size / 2
for layer in range(0, layer_count):


first = layer
last = size - first - 1


top_left = (first, first)
top_right = (first, last)
bottom_right = (last, last)
bottom_left = (last, first)


print 'top_left: %s' % (top_left)
print 'top_right: %s' % (top_right)
print 'bottom_right: %s' % (bottom_right)
print 'bottom_left: %s' % (bottom_left)


matrix = [
[0, 1, 2],
[3, 4, 5],
[6, 7, 8]
]


rotate(matrix)

输出应该是:

top_left: (0, 0)
top_right: (0, 2)
bottom_right: (2, 2)
bottom_left: (2, 0)

现在我们可以很容易地在我们的层循环中交换每个角:

def rotate(matrix):
size = len(matrix)
layer_count = size / 2
for layer in range(0, layer_count):
        

first = layer
last = size - first - 1


top_left = matrix[first][first]
top_right = matrix[first][last]
bottom_right = matrix[last][last]
bottom_left = matrix[last][first]


# bottom_left -> top_left
matrix[first][first] = bottom_left
# top_left -> top_right
matrix[first][last] = top_left
# top_right -> bottom_right
matrix[last][last] = top_right
# bottom_right -> bottom_left
matrix[last][first] = bottom_right




print_matrix(matrix)
print '---------'
rotate(matrix)
print_matrix(matrix)

转角前矩阵:

[0, 1, 2]
[3, 4, 5]
[6, 7, 8]

转角后矩阵:

[6, 1, 0]
[3, 4, 5]
[8, 7, 2]

太棒了!我们已经成功地旋转了矩阵的每个角。但是，我们没有旋转每层中间的元素。显然，我们需要一种在层内迭代的方法。

问题是，到目前为止，我们函数中唯一的循环(我们的层循环)在每次迭代时都移动到下一层。由于我们的矩阵只有一个可旋转的层，层循环在旋转角后退出。让我们看看一个更大的5×5矩阵(其中两个层需要旋转)会发生什么。函数代码略去，与前文相同:

matrix = [
[0, 1, 2, 3, 4],
[5, 6, 7, 8, 9],
[10, 11, 12, 13, 14],
[15, 16, 17, 18, 19],
[20, 21, 22, 23, 24]
]
print_matrix(matrix)
print '--------------------'
rotate(matrix)
print_matrix(matrix)

输出结果为:

[20,  1,  2,  3,  0]
[ 5, 16,  7,  6,  9]
[10, 11, 12, 13, 14]
[15, 18, 17,  8, 19]
[24, 21, 22, 23,  4]

最外层的角被旋转并不奇怪，但是，你可能也注意到下一层的角(向内)也被旋转了。这是有道理的。我们已经编写了代码来在层中导航，也可以旋转每个层的角。这感觉像是进步，但不幸的是，我们必须后退一步。在前一层(外层)完全旋转之前，移动到下一层是没有好处的。也就是说，直到层中的每个元素都被旋转。只旋转边角是不行的!

深呼吸。我们需要另一个循环。一个嵌套循环。新的嵌套循环将使用first和last变量，加上一个偏移量来在层内导航。我们将这个新循环称为“element loop”。元素循环将访问顶部一行的每个元素、右侧一行的每个元素、底部一行的每个元素和左侧一行的每个元素。

沿着顶部行向前移动需要列
向右移动要求行索引为李递增。< / >
沿着底部向后移动需要列
向左移动要求行索引为李递减。< / >

这听起来很复杂，但它很简单，因为我们为实现上述目标所增加和减少的次数在矩阵的四个边都是相同的。例如:

移动第一行的一个元素。
向右移动一个元素。
沿着最下面一行向后移动一个元素。
把一个元素移到左边。

这意味着我们可以将单个变量与first和last变量结合使用来在一层中移动。注意从上一行移动到右一行都需要递增，这可能会有所帮助。当沿着底部和左侧向上向后移动时，两者都需要递减。

def rotate(matrix):
size = len(matrix)
layer_count = size / 2
    

# Move through layers (i.e. layer loop).
for layer in range(0, layer_count):
        

first = layer
last = size - first - 1


# Move within a single layer (i.e. element loop).
for element in range(first, last):
            

offset = element - first


# 'element' increments column (across right)
top = (first, element)
# 'element' increments row (move down)
right_side = (element, last)
# 'last-offset' decrements column (across left)
bottom = (last, last-offset)
# 'last-offset' decrements row (move up)
left_side = (last-offset, first)


print 'top: %s' % (top)
print 'right_side: %s' % (right_side)
print 'bottom: %s' % (bottom)
print 'left_side: %s' % (left_side)

现在我们只需要将顶部分配给右侧，右侧分配给底部，底部分配给左侧，左侧分配给顶部。把这些放在一起，我们得到:

def rotate(matrix):
size = len(matrix)
layer_count = size / 2


for layer in range(0, layer_count):
first = layer
last = size - first - 1


for element in range(first, last):
offset = element - first


top = matrix[first][element]
right_side = matrix[element][last]
bottom = matrix[last][last-offset]
left_side = matrix[last-offset][first]


matrix[first][element] = left_side
matrix[element][last] = top
matrix[last][last-offset] = right_side
matrix[last-offset][first] = bottom

给定矩阵:

0,  1,  2
3,  4,  5
6,  7,  8

rotate函数的结果是:

6,  3,  0
7,  4,  1
8,  5,  2

小开

这是将数组旋转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

小开

@dimple发送的伟大算法的c#示例代码:

/* 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
*/

小开

下面是一个c#静态泛型方法，它可以为您完成这项工作。变量的名称很好，所以您可以很容易地理解算法的思想。

private static T[,] Rotate180 <T> (T[,] matrix)
{
var height = matrix.GetLength (0);
var width = matrix.GetLength (1);
var answer = new T[height, width];


for (int y = 0; y < height / 2; y++)
{
int topY = y;
int bottomY = height - 1 - y;
for (int topX = 0; topX < width; topX++)
{
var bottomX = width - topX - 1;
answer[topY, topX] = matrix[bottomY, bottomX];
answer[bottomY, bottomX] = matrix[topY, topX];
}
}


if (height % 2 == 0)
return answer;


var centerY = height / 2;
for (int leftX = 0; leftX < Mathf.CeilToInt(width / 2f); leftX++)
{
var rightX = width - 1 - leftX;
answer[centerY, leftX] = matrix[centerY, rightX];
answer[centerY, rightX] = matrix[centerY, leftX];
}


return answer;
}

小开

    public static void rotateMatrix(int[,] matrix)
{
//C#, to rotate an N*N matrix in place
int n = matrix.GetLength(0);
int layers =  n / 2;
int temp, temp2;


for (int i = 0; i < layers; i++) // for a 5 * 5 matrix, layers will be 2, since at layer three there would be only one element, (2,2), and we do not need to rotate it with itself
{
int offset = 0;
while (offset < n - 2 * i - 1)
{
// top right <- top left
temp = matrix[i + offset, n - i - 1]; //top right value when offset is zero
matrix[i + offset, n - i - 1] = matrix[i, i + offset];


//bottom right <- top right
temp2 = matrix[n - i - 1, n - i - 1 - offset]; //bottom right value when offset is zero
matrix[n - i - 1, n - i - 1 - offset] = temp;


//bottom left <- bottom right
temp = matrix[n - i - 1 - offset, i];
matrix[n - i - 1 - offset, i] = temp2;


//top left <- bottom left
matrix[i, i + offset] = temp;


offset++;
}
}
}

小开

很好的答案，但对于那些正在寻找DRY JavaScript代码的人- +90度和-90度:

          // Input: 1 2 3
//        4 5 6
//        7 8 9


// Transpose:
//       1 4 7
//       2 5 8
//       3 6 9


// Output:
// +90 Degree:
//       7 4 1
//       8 5 2
//       9 6 3


// -90 Degree:
//      3 6 9
//      2 5 8
//      1 4 7


// Rotate +90
function rotate90(matrix) {


matrix = transpose(matrix);
matrix.map(function(array) {
array.reverse();
});


return matrix;
}


// Rotate -90
function counterRotate90(matrix) {
var result = createEmptyMatrix(matrix.length);
matrix = transpose(matrix);
var counter = 0;


for (var i = matrix.length - 1; i >= 0; i--) {
result[counter] = matrix[i];
counter++;
}


return result;
}


// Create empty matrix
function createEmptyMatrix(len) {
var result = new Array();
for (var i = 0; i < len; i++) {
result.push([]);
}
return result;
}


// Transpose the matrix
function transpose(matrix) {
// make empty array
var len = matrix.length;
var result = createEmptyMatrix(len);


for (var i = 0; i < matrix.length; i++) {
for (var j = 0; j < matrix[i].length; j++) {
var temp = matrix[i][j];
result[j][i] = temp;
}
}
return result;
}






// Test Cases
var array1 = [
[1, 2],
[3, 4]
];
var array2 = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
];
var array3 = [
[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12],
[13, 14, 15, 16]
];


// +90 degress Rotation Tests


var test1 = rotate90(array1);
var test2 = rotate90(array2);
var test3 = rotate90(array3);
console.log(test1);
console.log(test2);
console.log(test3);


// -90 degress Rotation Tests
var test1 = counterRotate90(array1);
var test2 = counterRotate90(array2);
var test3 = counterRotate90(array3);
console.log(test1);
console.log(test2);
console.log(test3);

小开

可以做递归相当干净，这里是我的实现在golang!

在没有额外内存的情况下递归地旋转go golang中的NXN矩阵

func rot90(a [][]int) {
n := len(a)
if n == 1 {
return
}
for i := 0; i < n; i++ {
a[0][i], a[n-1-i][n-1] = a[n-1-i][n-1], a[0][i]
}
rot90(a[1:])
}

小开

在Java中

public class Matrix {
/* Author Shrikant Dande */
private static void showMatrix(int[][] arr,int rows,int col){


for(int i =0 ;i<rows;i++){
for(int j =0 ;j<col;j++){
System.out.print(arr[i][j]+" ");
}
System.out.println();
}


}


private static void rotateMatrix(int[][] arr,int rows,int col){


int[][] tempArr = new int[4][4];
for(int i =0 ;i<rows;i++){
for(int j =0 ;j<col;j++){
tempArr[i][j] = arr[rows-1-j][i];
System.out.print(tempArr[i][j]+" ");
}
System.out.println();
}


}
public static void main(String[] args) {
int[][] arr = { {1,  2,  3,  4},
{5,  6,  7,  8},
{9,  1, 2, 5},
{7, 4, 8, 9}};
int rows = 4,col = 4;


showMatrix(arr, rows, col);
System.out.println("------------------------------------------------");
rotateMatrix(arr, rows, col);


}

｝

小开

这是一个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

小开

试试我的库AbacusUtil:

@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();
}

小开

PHP解决方案为顺时针&逆时针方向

$aMatrix = array(
array( 1, 2, 3 ),
array( 4, 5, 6 ),
array( 7, 8, 9 )
);


function CounterClockwise( $aMatrix )
{
$iCount  = count( $aMatrix );
$aReturn = array();
for( $y = 0; $y < $iCount; ++$y )
{
for( $x = 0; $x < $iCount; ++$x )
{
$aReturn[ $iCount - $x - 1 ][ $y ] = $aMatrix[ $y ][ $x ];
}
}
return $aReturn;
}


function Clockwise( $aMatrix )
{
$iCount  = count( $aMatrix );
$aReturn = array();
for( $y = 0; $y < $iCount; ++$y )
{
for( $x = 0; $x < $iCount; ++$x )
{
$aReturn[ $x ][ $iCount - $y - 1 ] = $aMatrix[ $y ][ $x ];
}
}
return $aReturn;
}


function printMatrix( $aMatrix )
{
$iCount = count( $aMatrix );
for( $x = 0; $x < $iCount; ++$x )
{
for( $y = 0; $y < $iCount; ++$y )
{
echo $aMatrix[ $x ][ $y ];
echo " ";
}
echo "\n";
}
}
printMatrix( $aMatrix );
echo "\n";
$aNewMatrix = CounterClockwise( $aMatrix );
printMatrix( $aNewMatrix );
echo "\n";
$aNewMatrix = Clockwise( $aMatrix );
printMatrix( $aNewMatrix );

小开

矩阵转置的C代码;旋转(+/-90，+/-180)

支持方阵和非方阵，具有原位和复制功能
支持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;
}
}

｀

小开

基于大量的其他答案，我用c#想出了这个:

/// <param name="rotation">The number of rotations (if negative, the <see cref="Matrix{TValue}"/> is rotated counterclockwise;
/// otherwise, it's rotated clockwise). A single (positive) rotation is equivalent to 90° or -270°; a single (negative) rotation is
/// equivalent to -90° or 270°. Matrices may be rotated by 90°, 180°, or 270° only (or multiples thereof).</param>
/// <returns></returns>
public Matrix<TValue> Rotate(int rotation)
{
var result = default(Matrix<TValue>);


//This normalizes the requested rotation (for instance, if 10 is specified, the rotation is actually just +-2 or +-180°, but all
//correspond to the same rotation).
var d = rotation.ToDouble() / 4d;
d = d - (int)d;


var degree = (d - 1d) * 4d;


//This gets the type of rotation to make; there are a total of four unique rotations possible (0°, 90°, 180°, and 270°).
//Each correspond to 0, 1, 2, and 3, respectively (or 0, -1, -2, and -3, if in the other direction). Since
//1 is equivalent to -3 and so forth, we combine both cases into one.
switch (degree)
{
case -3:
case +1:
degree = 3;
break;
case -2:
case +2:
degree = 2;
break;
case -1:
case +3:
degree = 1;
break;
case -4:
case  0:
case +4:
degree = 0;
break;
}
switch (degree)
{
//The rotation is 0, +-180°
case 0:
case 2:
result = new TValue[Rows, Columns];
break;
//The rotation is +-90°
case 1:
case 3:
result = new TValue[Columns, Rows];
break;
}


for (uint i = 0; i < Columns; ++i)
{
for (uint j = 0; j < Rows; ++j)
{
switch (degree)
{
//If rotation is 0°
case 0:
result._values[j][i] = _values[j][i];
break;
//If rotation is -90°
case 1:
//Transpose, then reverse each column OR reverse each row, then transpose
result._values[i][j] = _values[j][Columns - i - 1];
break;
//If rotation is +-180°
case 2:
//Reverse each column, then reverse each row
result._values[(Rows - 1) - j][(Columns - 1) - i] = _values[j][i];
break;
//If rotation is +90°
case 3:
//Transpose, then reverse each row
result._values[i][j] = _values[Rows - j - 1][i];
break;
}
}
}
return result;
}

其中_values对应于由Matrix<TValue>定义的私有二维数组(以[][]的形式)。result = new TValue[Columns, Rows]可以通过隐式操作符重载实现，并将二维数组转换为Matrix<TValue>。 Columns和Rows两个属性是公共属性，用于获取当前实例的列数和行数:

public uint Columns
=> (uint)_values[0].Length;


public uint Rows
=> (uint)_values.Length;

当然，假设您更喜欢使用无符号下标;-)

所有这些都允许您指定它应该旋转多少次，以及它应该向左旋转(如果小于零)还是向右旋转(如果大于零)。您可以改进此方法，以检查实际角度的旋转，但如果值不是90的倍数，则可能会抛出异常。有了这些输入，你可以相应地改变方法:

public Matrix<TValue> Rotate(int rotation)
{
var _rotation = (double)rotation / 90d;


if (_rotation - Math.Floor(_rotation) > 0)
{
throw new NotSupportedException("A matrix may only be rotated by multiples of 90.").
}


rotation = (int)_rotation;
...
}

由于用double比int更准确地表示度，但矩阵只能以90的倍数旋转，因此使参数对应于可以用所使用的数据结构准确表示的其他东西要直观得多。int是完美的，因为它可以告诉你旋转多少次，直到某个单位(90)以及方向。double很可能也能告诉你这一点，但它也包括了这个操作不支持的值(这本质上是反直觉的)。

小开

基于社区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
}

小开

这个解决方案不关心正方形或矩形的尺寸，你可以旋转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 (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
}

基本上，我们转换源数组下标:

__abc0 =>

然后，使用这个转换后的indexes数组，将实际值放入最终的rotated数组中。

下面是一些测试用例:

//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]

小开

在特征 (c++)中:

Eigen::Matrix2d mat;
mat <<  1, 2,
3, 4;
std::cout << mat << "\n\n";


Eigen::Matrix2d r_plus_90 = mat.transpose().rowwise().reverse();
std::cout << r_plus_90 << "\n\n";


Eigen::Matrix2d r_minus_90 = mat.transpose().colwise().reverse();
std::cout << r_minus_90 << "\n\n";


Eigen::Matrix2d r_180 = mat.colwise().reverse().rowwise().reverse(); // +180 same as -180
std::cout << r_180 << "\n\n";

输出:

小开

顺时针或逆时针旋转2D数组的常用方法。

首先颠倒上下，然后交换对称

1 2 3     7 8 9     7 4 1
4 5 6  => 4 5 6  => 8 5 2
7 8 9     1 2 3     9 6 3

void rotate(vector<vector<int> > &matrix) {
reverse(matrix.begin(), matrix.end());
for (int i = 0; i < matrix.size(); ++i) {
for (int j = i + 1; j < matrix[i].size(); ++j)
swap(matrix[i][j], matrix[j][i]);
}
}

先从左到右反向，然后交换对称

1 2 3     3 2 1     3 6 9
4 5 6  => 6 5 4  => 2 5 8
7 8 9     9 8 7     1 4 7

void anti_rotate(vector<vector<int> > &matrix) {
for (auto vi : matrix) reverse(vi.begin(), vi.end());
for (int i = 0; i < matrix.size(); ++i) {
for (int j = i + 1; j < matrix[i].size(); ++j)
swap(matrix[i][j], matrix[j][i]);
}
}

小开

在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)