受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呢?
受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呢?
当前回答
下面是一个原地旋转的数组,而不是使用一个全新的数组来保存结果。我已经停止了数组的初始化和输出。这只适用于正方形数组,但它们可以是任何大小。内存开销等于数组中一个元素的大小,因此您可以对任意大的数组进行旋转。
int a[4][4];
int n = 4;
int tmp;
for (int i = 0; i < n / 2; i++)
{
for (int j = i; j < n - i - 1; j++)
{
tmp = a[i][j];
a[i][j] = a[j][n-i-1];
a[j][n-i-1] = a[n-i-1][n-j-1];
a[n-i-1][n-j-1] = a[n-j-1][i];
a[n-j-1][i] = tmp;
}
}
其他回答
/* 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);
}
这是一个如今被高估的面试问题。
我的建议是:不要让面试官用他们关于解决这个问题的疯狂建议把你弄糊涂了。使用白板绘制输入数组的索引,然后绘制输出数组的索引。旋转前后的列分度示例如下:
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);
}
}
#!/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]]
基于大量的其他答案,我用c#想出了这个:
/// <param name="rotation">The number of rotations (if negative, the <see cref="Matrix{TValue}"/> is rotated counterclockwise;
/// otherwise, it's rotated clockwise). A single (positive) rotation is equivalent to 90° or -270°; a single (negative) rotation is
/// equivalent to -90° or 270°. Matrices may be rotated by 90°, 180°, or 270° only (or multiples thereof).</param>
/// <returns></returns>
public Matrix<TValue> Rotate(int rotation)
{
var result = default(Matrix<TValue>);
//This normalizes the requested rotation (for instance, if 10 is specified, the rotation is actually just +-2 or +-180°, but all
//correspond to the same rotation).
var d = rotation.ToDouble() / 4d;
d = d - (int)d;
var degree = (d - 1d) * 4d;
//This gets the type of rotation to make; there are a total of four unique rotations possible (0°, 90°, 180°, and 270°).
//Each correspond to 0, 1, 2, and 3, respectively (or 0, -1, -2, and -3, if in the other direction). Since
//1 is equivalent to -3 and so forth, we combine both cases into one.
switch (degree)
{
case -3:
case +1:
degree = 3;
break;
case -2:
case +2:
degree = 2;
break;
case -1:
case +3:
degree = 1;
break;
case -4:
case 0:
case +4:
degree = 0;
break;
}
switch (degree)
{
//The rotation is 0, +-180°
case 0:
case 2:
result = new TValue[Rows, Columns];
break;
//The rotation is +-90°
case 1:
case 3:
result = new TValue[Columns, Rows];
break;
}
for (uint i = 0; i < Columns; ++i)
{
for (uint j = 0; j < Rows; ++j)
{
switch (degree)
{
//If rotation is 0°
case 0:
result._values[j][i] = _values[j][i];
break;
//If rotation is -90°
case 1:
//Transpose, then reverse each column OR reverse each row, then transpose
result._values[i][j] = _values[j][Columns - i - 1];
break;
//If rotation is +-180°
case 2:
//Reverse each column, then reverse each row
result._values[(Rows - 1) - j][(Columns - 1) - i] = _values[j][i];
break;
//If rotation is +90°
case 3:
//Transpose, then reverse each row
result._values[i][j] = _values[Rows - j - 1][i];
break;
}
}
}
return result;
}
其中_values对应于由Matrix<TValue>定义的私有二维数组(形式为[][])。result = new TValue[Columns, Rows]可能通过隐式操作符重载并将二维数组转换为Matrix<TValue>。 Columns和Rows两个属性是公共属性,用于获取当前实例的列数和行数:
public uint Columns
=> (uint)_values[0].Length;
public uint Rows
=> (uint)_values.Length;
当然,假设您更喜欢使用无符号下标;-)
所有这些都允许您指定它应该旋转多少次,以及它应该向左旋转(如果小于零)还是向右旋转(如果大于零)。您可以改进此方法,以检查实际角度的旋转,但如果值不是90的倍数,则可能会抛出异常。有了这些输入,你可以相应地改变方法:
public Matrix<TValue> Rotate(int rotation)
{
var _rotation = (double)rotation / 90d;
if (_rotation - Math.Floor(_rotation) > 0)
{
throw new NotSupportedException("A matrix may only be rotated by multiples of 90.").
}
rotation = (int)_rotation;
...
}
Since a degree is more accurately expressed by double than int, but a matrix can only rotate in multiples of 90, it is far more intuitive to make the argument correspond to something else that can be accurately represented by the data structure used. int is perfect because it can tell you how many times to rotate it up to a certain unit (90) as well as the direction. double may very well be able to tell you that also, but it also includes values that aren't supported by this operation (which is inherently counter-intuitive).
可以做递归相当干净,这里是我的实现在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:])
}