受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呢?
当前回答
虽然旋转数据可能是必要的(也许是为了更新物理存储的表示),但在数组访问上添加一层间接层(也许是一个接口)会变得更简单,可能更性能:
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.
与所有性能问题一样,测量,测量,测量!
其他回答
顺时针或逆时针旋转2D数组的常用方法。
顺时针旋转 首先颠倒上下,然后交换对称 1 2 3 7 8 9 7 4 4 5 6 => 4 5 6 => 8 5 7 8 9 1 2 3 9 6 3
void rotate(vector<vector<int> > &matrix) {
reverse(matrix.begin(), matrix.end());
for (int i = 0; i < matrix.size(); ++i) {
for (int j = i + 1; j < matrix[i].size(); ++j)
swap(matrix[i][j], matrix[j][i]);
}
}
逆时针方向旋转 首先从左到右反向,然后交换对称 1 2 3 3 2 1 3 6 9 4 5 6 => 6 5 4 => 2 5 7 8 9 9 8 7 1 4 7
void anti_rotate(vector<vector<int> > &matrix) {
for (auto vi : matrix) reverse(vi.begin(), vi.end());
for (int i = 0; i < matrix.size(); ++i) {
for (int j = i + 1; j < matrix[i].size(); ++j)
swap(matrix[i][j], matrix[j][i]);
}
}
我只用一个循环就能做到。时间复杂度看起来像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]
我的旋转版本:
void rotate_matrix(int *matrix, int size)
{
int result[size*size];
for (int i = 0; i < size; ++i)
for (int j = 0; j < size; ++j)
result[(size - 1 - i) + j*size] = matrix[i*size+j];
for (int i = 0; i < size*size; ++i)
matrix[i] = result[i];
}
在其中,我们将最后一列改为第一行,以此类推。这可能不是最理想的,但对于理解来说是清楚的。
你可以通过3个简单步骤做到这一点:
1)假设我们有一个矩阵
1 2 3
4 5 6
7 8 9
2)求矩阵的转置
1 4 7
2 5 8
3 6 9
3)交换行得到旋转矩阵
3 6 9
2 5 8
1 4 7
Java源代码:
public class MyClass {
public static void main(String args[]) {
Demo obj = new Demo();
/*initial matrix to rotate*/
int[][] matrix = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } };
int[][] transpose = new int[3][3]; // matrix to store transpose
obj.display(matrix); // initial matrix
obj.rotate(matrix, transpose); // call rotate method
System.out.println();
obj.display(transpose); // display the rotated matix
}
}
class Demo {
public void rotate(int[][] mat, int[][] tran) {
/* First take the transpose of the matrix */
for (int i = 0; i < mat.length; i++) {
for (int j = 0; j < mat.length; j++) {
tran[i][j] = mat[j][i];
}
}
/*
* Interchange the rows of the transpose matrix to get rotated
* matrix
*/
for (int i = 0, j = tran.length - 1; i != j; i++, j--) {
for (int k = 0; k < tran.length; k++) {
swap(i, k, j, k, tran);
}
}
}
public void swap(int a, int b, int c, int d, int[][] arr) {
int temp = arr[a][b];
arr[a][b] = arr[c][d];
arr[c][d] = temp;
}
/* Method to display the matrix */
public void display(int[][] arr) {
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length; j++) {
System.out.print(arr[i][j] + " ");
}
System.out.println();
}
}
}
输出:
1 2 3
4 5 6
7 8 9
3 6 9
2 5 8
1 4 7
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;
}