受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;
}
其他回答
下面是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;
}
}
}
#转置是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)的解更好，但只适用于特殊构造的矩阵(如稀疏矩阵)
这是我对矩阵90度旋转的尝试，这是c中的2步解决方案，首先转置矩阵，然后交换cols。
#define ROWS 5
#define COLS 5
void print_matrix_b(int B[][COLS], int rows, int cols)
{
for (int i = 0; i <= rows; i++) {
for (int j = 0; j <=cols; j++) {
printf("%d ", B[i][j]);
}
printf("\n");
}
}
void swap_columns(int B[][COLS], int l, int r, int rows)
{
int tmp;
for (int i = 0; i <= rows; i++) {
tmp = B[i][l];
B[i][l] = B[i][r];
B[i][r] = tmp;
}
}
void matrix_2d_rotation(int B[][COLS], int rows, int cols)
{
int tmp;
// Transpose the matrix first
for (int i = 0; i <= rows; i++) {
for (int j = i; j <=cols; j++) {
tmp = B[i][j];
B[i][j] = B[j][i];
B[j][i] = tmp;
}
}
// Swap the first and last col and continue until
// the middle.
for (int i = 0; i < (cols / 2); i++)
swap_columns(B, i, cols - i, rows);
}
int _tmain(int argc, _TCHAR* argv[])
{
int B[ROWS][COLS] = {
{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}
};
matrix_2d_rotation(B, ROWS - 1, COLS - 1);
print_matrix_b(B, ROWS - 1, COLS -1);
return 0;
}
这是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;
}
下面是PHP的递归方法:
$m = array();
$m[0] = array('a', 'b', 'c');
$m[1] = array('d', 'e', 'f');
$m[2] = array('g', 'h', 'i');
$newMatrix = array();
function rotateMatrix($m, $i = 0, &$newMatrix)
{
foreach ($m as $chunk) {
$newChunk[] = $chunk[$i];
}
$newMatrix[] = array_reverse($newChunk);
$i++;
if ($i < count($m)) {
rotateMatrix($m, $i, $newMatrix);
}
}
rotateMatrix($m, 0, $newMatrix);
echo '<pre>';
var_dump($newMatrix);
echo '<pre>';
