受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呢?
当前回答
这里有大量的好代码,但我只是想以几何形式展示,这样你就能更好地理解代码逻辑。以下是我的处理方法。
首先,不要把这和换位相混淆,换位是很容易的。
基本的想法是把它当作层,我们一次旋转一个层。
假设我们有一辆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
然后我们旋转下面这个有点歪斜的菱形
2
8
9
15
然后是第二个斜菱形
3
5
12
14
这就搞定了外缘基本上我们一次做一个壳层直到
最后是中间的方块(如果是奇数则是最后一个不动的元素)
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(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]
正如我在上一篇文章中所说的,这里有一些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。对构造函数稍加更改,创建一个新数组并将值复制到该数组中,就可以将其整理出来。
#转置是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)的解更好,但只适用于特殊构造的矩阵(如稀疏矩阵)
我的旋转版本:
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];
}
在其中,我们将最后一列改为第一行,以此类推。这可能不是最理想的,但对于理解来说是清楚的。
在原地顺时针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;
}