受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呢?
当前回答
虽然旋转数据可能是必要的(也许是为了更新物理存储的表示)，但在数组访问上添加一层间接层(也许是一个接口)会变得更简单，可能更性能:
interface IReadableMatrix
{
int GetValue(int x, int y);
}
如果你的矩阵已经实现了这个接口，那么它可以通过这样一个装饰器类来旋转:
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度，水平/垂直翻转和缩放都可以以这种方式实现。
Performance would need to be measured in your specific scenario. However the O(n^2) operation has now been replaced with an O(1) call. It's a virtual method call which is slower than direct array access, so it depends upon how frequently the rotated array is used after rotation. If it's used once, then this approach would definitely win. If it's rotated then used in a long-running system for days, then in-place rotation might perform better. It also depends whether you can accept the up-front cost.
与所有性能问题一样，测量，测量，测量!
其他回答
从线性的角度来看，考虑以下矩阵:
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'的作用。 分别为:
7 4 1 3 6 9
A'B = 8 5 2 BA' = 2 5 8
9 6 3 1 4 7
这对任何nxn矩阵都是可展开的。 在代码中快速应用这个概念:
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);
}
}
}
这是一个如今被高估的面试问题。
我的建议是:不要让面试官用他们关于解决这个问题的疯狂建议把你弄糊涂了。使用白板绘制输入数组的索引，然后绘制输出数组的索引。旋转前后的列分度示例如下:
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);
}
}
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++;
}
}
}
你可以通过3个简单步骤做到这一点:
1)假设我们有一个矩阵
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();
}
}
}
输出:
1 2 3
4 5 6
7 8 9
3 6 9
2 5 8
1 4 7
这是将数组旋转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
