受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版本:
public static void rightRotate(int[][] matrix, int n) {
for (int layer = 0; layer < n / 2; layer++) {
int first = layer;
int last = n - 1 - first;
for (int i = first; i < last; i++) {
int offset = i - first;
int temp = matrix[first][i];
matrix[first][i] = matrix[last-offset][first];
matrix[last-offset][first] = matrix[last][last-offset];
matrix[last][last-offset] = matrix[i][last];
matrix[i][last] = temp;
}
}
}
该方法首先旋转最外层，然后按顺序移动到内层。
其他回答
/* 90-degree clockwise:
temp_array = left_col
left_col = bottom_row
bottom_row = reverse(right_col)
reverse(right_col) = reverse(top_row)
reverse(top_row) = temp_array
*/
void RotateClockwise90(int ** arr, int lo, int hi) {
if (lo >= hi)
return;
for (int i=lo; i<hi; i++) {
int j = lo+hi-i;
int temp = arr[i][lo];
arr[i][lo] = arr[hi][i];
arr[hi][i] = arr[j][hi];
arr[j][hi] = arr[lo][j];
arr[lo][j] = temp;
}
RotateClockwise90(arr, lo+1, hi-1);
}
PHP解决方案为顺时针和逆时针
$aMatrix = array(
array( 1, 2, 3 ),
array( 4, 5, 6 ),
array( 7, 8, 9 )
);
function CounterClockwise( $aMatrix )
{
$iCount = count( $aMatrix );
$aReturn = array();
for( $y = 0; $y < $iCount; ++$y )
{
for( $x = 0; $x < $iCount; ++$x )
{
$aReturn[ $iCount - $x - 1 ][ $y ] = $aMatrix[ $y ][ $x ];
}
}
return $aReturn;
}
function Clockwise( $aMatrix )
{
$iCount = count( $aMatrix );
$aReturn = array();
for( $y = 0; $y < $iCount; ++$y )
{
for( $x = 0; $x < $iCount; ++$x )
{
$aReturn[ $x ][ $iCount - $y - 1 ] = $aMatrix[ $y ][ $x ];
}
}
return $aReturn;
}
function printMatrix( $aMatrix )
{
$iCount = count( $aMatrix );
for( $x = 0; $x < $iCount; ++$x )
{
for( $y = 0; $y < $iCount; ++$y )
{
echo $aMatrix[ $x ][ $y ];
echo " ";
}
echo "\n";
}
}
printMatrix( $aMatrix );
echo "\n";
$aNewMatrix = CounterClockwise( $aMatrix );
printMatrix( $aNewMatrix );
echo "\n";
$aNewMatrix = Clockwise( $aMatrix );
printMatrix( $aNewMatrix );
下面是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>';
我只用一个循环就能做到。时间复杂度看起来像O(K)其中K是数组中的所有元素。 下面是我用JavaScript做的:
首先，我们用一个数组来表示n^2矩阵。然后，像这样迭代它:
/**
* Rotates matrix 90 degrees clockwise
* @param arr: the source array
* @param n: the array side (array is square n^2)
*/
function rotate (arr, n) {
var rotated = [], indexes = []
for (var i = 0; i < arr.length; i++) {
if (i < n)
indexes[i] = i * n + (n - 1)
else
indexes[i] = indexes[i - n] - 1
rotated[indexes[i]] = arr[i]
}
return rotated
}
基本上，我们转换源数组下标:
[0,1,2,3,4,5,6,7,8] => [2,5,8,1,4,7,0,3 6]
然后，使用这个转换后的索引数组，我们将实际值放在最终旋转的数组中。
下面是一些测试用例:
//n=3
rotate([
1, 2, 3,
4, 5, 6,
7, 8, 9], 3))
//result:
[7, 4, 1,
8, 5, 2,
9, 6, 3]
//n=4
rotate([
1, 2, 3, 4,
5, 6, 7, 8,
9, 10, 11, 12,
13, 14, 15, 16], 4))
//result:
[13, 9, 5, 1,
14, 10, 6, 2,
15, 11, 7, 3,
16, 12, 8, 4]
//n=5
rotate([
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], 5))
//result:
[21, 16, 11, 6, 1,
22, 17, 12, 7, 2,
23, 18, 13, 8, 3,
24, 19, 14, 9, 4,
25, 20, 15, 10, 5]
时间- O(N)，空间- O(1)
public void rotate(int[][] matrix) {
int n = matrix.length;
for (int i = 0; i < n / 2; i++) {
int last = n - 1 - i;
for (int j = i; j < last; j++) {
int top = matrix[i][j];
matrix[i][j] = matrix[last - j][i];
matrix[last - j][i] = matrix[last][last - j];
matrix[last][last - j] = matrix[j][last];
matrix[j][last] = top;
}
}
}
