受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呢?
当前回答
在Eigen (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";
输出:
1 2
3 4
3 1
4 2
2 4
1 3
4 3
2 1
其他回答
在Eigen (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";
输出:
1 2
3 4
3 1
4 2
2 4
1 3
4 3
2 1
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#的
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;
}
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
这是一个如今被高估的面试问题。
我的建议是:不要让面试官用他们关于解决这个问题的疯狂建议把你弄糊涂了。使用白板绘制输入数组的索引，然后绘制输出数组的索引。旋转前后的列分度示例如下:
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);
}
}
