受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呢?
当前回答
#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];
}
}
其他回答
可以做递归相当干净，这里是我的实现在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中的一个更好的版本:我已经为一个具有不同宽度和高度的矩阵制作了它
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的帖子。
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]的位置将使列表在矩阵的不同层次上颠倒。
下面是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;
}
}
}
这是一个如今被高估的面试问题。
我的建议是:不要让面试官用他们关于解决这个问题的疯狂建议把你弄糊涂了。使用白板绘制输入数组的索引，然后绘制输出数组的索引。旋转前后的列分度示例如下:
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);
}
}
