受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呢?
当前回答
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 );
其他回答
可以做递归相当干净，这里是我的实现在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:])
}
PHP:
array_unshift($array, null);
$array = call_user_func_array("array_map", $array);
如果你需要旋转矩形二维阵列90度，在上面的代码之前或之后添加以下一行(取决于你需要的旋转方向):
$array = array_reverse($array);
#!/usr/bin/env python
original = [ [1,2,3],
[4,5,6],
[7,8,9] ]
# Rotate matrix 90 degrees...
for i in map(None,*original[::-1]):
print str(i) + '\n'
这导致双方旋转90度(即。123(上面)现在是741(左边)。
这个Python解决方案是可行的，因为它使用了带负步的切片来反转行顺序(将7移到最上面)
original = [ [7,8,9],
[4,5,6],
[1,2,3] ]
然后，它使用map(以及隐含的标识函数，这是map以None作为第一个参数的结果)和*按顺序解包所有元素，重新组合列(即。第一个元素一起放在一个元组中，第二个元素一起放在一个元组中，以此类推)。你有效地得到得到返回如下重组:
original = [[7,8,9],
[4,5,6],
[1,2,3]]
这是一个如今被高估的面试问题。
我的建议是:不要让面试官用他们关于解决这个问题的疯狂建议把你弄糊涂了。使用白板绘制输入数组的索引，然后绘制输出数组的索引。旋转前后的列分度示例如下:
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);
}
}
已经有很多答案了，我发现两个声称O(1)时间复杂度。真正的O(1)算法是保持数组存储不变，并改变索引其元素的方式。这里的目标是不消耗额外的内存，也不需要额外的时间来迭代数据。
旋转90度，-90度和180度是简单的转换，只要你知道你的2D数组中有多少行和列就可以执行;要将任何向量旋转90度，交换轴并与Y轴相反。对于-90度，交换轴和X轴。对于180度，两个坐标轴都是负的，不交换。
进一步的转换是可能的，例如通过独立地否定轴来水平和/或垂直地镜像。
这可以通过访问器方法来实现。下面的例子是JavaScript函数，但是这些概念同样适用于所有语言。
//按列/行顺序获取数组元素 var getArray2d =函数(a, x, y) { 返回一个[y] [x]; }; / /演示 Var arr = [ [5,4,6]， [1,7,9]， [- 2,11,0]， [8,21， -3]， [3， -1, 2] ]; Var newar = []; arr[0]. foreach (() => newarr。push(新数组(arr.length))); For (var I = 0;I < newar .length;我+ +){ For (var j = 0;J < newarr[0].length;j + +) { newarr[i][j] = getArray2d(arr, i, j); ｝ ｝ console.log (newarr);
// Get an array element rotated 90 degrees clockwise function getArray2dCW(a, x, y) { var t = x; x = y; y = a.length - t - 1; return a[y][x]; } //demo var arr = [ [5, 4, 6], [1, 7, 9], [-2, 11, 0], [8, 21, -3], [3, -1, 2] ]; var newarr = []; arr[0].forEach(() => newarr.push(new Array(arr.length))); for (var i = 0; i < newarr[0].length; i++) { for (var j = 0; j < newarr.length; j++) { newarr[j][i] = getArray2dCW(arr, i, j); } } console.log(newarr);
// Get an array element rotated 90 degrees counter-clockwise function getArray2dCCW(a, x, y) { var t = x; x = a[0].length - y - 1; y = t; return a[y][x]; } //demo var arr = [ [5, 4, 6], [1, 7, 9], [-2, 11, 0], [8, 21, -3], [3, -1, 2] ]; var newarr = []; arr[0].forEach(() => newarr.push(new Array(arr.length))); for (var i = 0; i < newarr[0].length; i++) { for (var j = 0; j < newarr.length; j++) { newarr[j][i] = getArray2dCCW(arr, i, j); } } console.log(newarr);
// Get an array element rotated 180 degrees function getArray2d180(a, x, y) { x = a[0].length - x - 1; y = a.length - y - 1; return a[y][x]; } //demo var arr = [ [5, 4, 6], [1, 7, 9], [-2, 11, 0], [8, 21, -3], [3, -1, 2] ]; var newarr = []; arr.forEach(() => newarr.push(new Array(arr[0].length))); for (var i = 0; i < newarr[0].length; i++) { for (var j = 0; j < newarr.length; j++) { newarr[j][i] = getArray2d180(arr, i, j); } } console.log(newarr);
这段代码假设有一个嵌套数组的数组，其中每个内部数组都是一行。
该方法允许您读取(或写入)元素(甚至是随机顺序)，就像数组已经旋转或转换一样。现在只要选择正确的函数来调用，可能是通过引用，然后就可以了!
这个概念可以扩展为通过访问器方法附加地(非破坏性地)应用转换。包括任意角度旋转和缩放。
