受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呢?
当前回答
这是一个空间旋转方法，由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;
}
其他回答
虽然旋转数据可能是必要的(也许是为了更新物理存储的表示)，但在数组访问上添加一层间接层(也许是一个接口)会变得更简单，可能更性能:
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.
与所有性能问题一样，测量，测量，测量!
原地旋转不可能比O(n²)更快，原因是如果我们想旋转矩阵，我们必须至少一次触及所有n²元素，无论你实现什么算法。
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]
]
这是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;
}
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;
}
