受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呢?


当前回答

对于i:= 0到X 对于j:= 0到X做 [j][i]:= graphic2[X-i][j]

X是图形所在数组的大小。

其他回答

在原地顺时针90度旋转使用矢量矢量..

 #include<iostream>
 #include<vector>
 #include<algorithm>
 using namespace std;
 //Rotate a Matrix by 90 degrees
void rotateMatrix(vector<vector<int> > &matrix){
   int n=matrix.size();
   for(int i=0;i<n;i++){
    for(int j=i+1;j<n;j++){
        swap(matrix[i][j],matrix[j][i]);
    }
 }
     for(int i=0;i<n;i++){
        reverse(matrix[i].begin(),matrix[i].end());
       }
   }

    int main(){

   int n;
   cout<<"enter the size of the matrix:"<<endl;
     while (cin >> n) {
    vector< vector<int> > m;
      cout<<"enter the elements"<<endl;
    for (int i = 0; i < n; i++) {
        m.push_back(vector<int>(n));
        for (int j = 0; j < n; j++)
            scanf("%d", &m[i][j]);
    }
      cout<<"the rotated matrix is:"<<endl;
      rotateMatrix(m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            cout << m[i][j] << ' ';
        cout << endl;
    }
   }
   return 0;
 }

下面是我的Ruby版本(注意,值显示的不一样,但它仍然按照描述旋转)。

def rotate(matrix)
  result = []
  4.times { |x|
    result[x] = []
    4.times { |y|
      result[x][y] = matrix[y][3 - x]
    }
  }

  result
end

matrix = []
matrix[0] = [1,2,3,4]
matrix[1] = [5,6,7,8]
matrix[2] = [9,0,1,2]
matrix[3] = [3,4,5,6]

def print_matrix(matrix)
  4.times { |y|
    4.times { |x|
      print "#{matrix[x][y]} "
    }
    puts ""
  }
end

print_matrix(matrix)
puts ""
print_matrix(rotate(matrix))

输出:

1 5 9 3 
2 6 0 4 
3 7 1 5 
4 8 2 6 

4 3 2 1 
8 7 6 5 
2 1 0 9 
6 5 4 3

虽然旋转数据可能是必要的(也许是为了更新物理存储的表示),但在数组访问上添加一层间接层(也许是一个接口)会变得更简单,可能更性能:

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.

与所有性能问题一样,测量,测量,测量!

从线性的角度来看,考虑以下矩阵:

    1 2 3        0 0 1
A = 4 5 6    B = 0 1 0
    7 8 9        1 0 0

现在求A

     1 4 7
A' = 2 5 8
     3 6 9

考虑A'对B的作用,或B对A'的作用。 分别为:

      7 4 1          3 6 9
A'B = 8 5 2    BA' = 2 5 8
      9 6 3          1 4 7

这对任何nxn矩阵都是可展开的。 在代码中快速应用这个概念:

void swapInSpace(int** mat, int r1, int c1, int r2, int c2)
{
    mat[r1][c1] ^= mat[r2][c2];
    mat[r2][c2] ^= mat[r1][c1];
    mat[r1][c1] ^= mat[r2][c2];
}

void transpose(int** mat, int size)
{
    for (int i = 0; i < size; i++)
    {
        for (int j = (i + 1); j < size; j++)
        {
            swapInSpace(mat, i, j, j, i);
        }
    }
}

void rotate(int** mat, int size)
{
    //Get transpose
    transpose(mat, size);

    //Swap columns
    for (int i = 0; i < size / 2; i++)
    {
        for (int j = 0; j < size; j++)
        {
            swapInSpace(mat, i, j, size - (i + 1), j);
        }
    }
}

矩阵转置和旋转(+/-90,+/-180)的C代码

支持方阵和非方阵,具有原位和复制功能 支持2D数组和带有逻辑行/cols的1D指针 单元测试;有关使用示例,请参阅测试 测试gcc -std=c90 -Wall -pedantic, MSVC17

`

#include <stdlib.h>
#include <memory.h>
#include <assert.h>

/* 
    Matrix transpose & rotate (+/-90, +/-180)
        Supports both 2D arrays and 1D pointers with logical rows/cols
        Supports square and non-square matrices, has in-place and copy features
        See tests for examples of usage
    tested gcc -std=c90 -Wall -pedantic, MSVC17
*/

typedef int matrix_data_t;  /* matrix data type */

void transpose(const matrix_data_t* src, matrix_data_t* dst, int rows, int cols);
void transpose_inplace(matrix_data_t* data, int n );
void rotate(int direction, const matrix_data_t* src, matrix_data_t* dst, int rows, int cols);
void rotate_inplace(int direction, matrix_data_t* data, int n);
void reverse_rows(matrix_data_t* data, int rows, int cols);
void reverse_cols(matrix_data_t* data, int rows, int cols);

/* test/compare fn */
int test_cmp(const matrix_data_t* lhs, const matrix_data_t* rhs, int rows, int cols );

/* TESTS/USAGE */
void transpose_test() {

    matrix_data_t sq3x3[9] = { 0,1,2,3,4,5,6,7,8 };/* 3x3 square, odd length side */
    matrix_data_t sq3x3_cpy[9];
    matrix_data_t sq3x3_2D[3][3] = { { 0,1,2 },{ 3,4,5 },{ 6,7,8 } };/* 2D 3x3 square */
    matrix_data_t sq3x3_2D_copy[3][3];

    /* expected test values */
    const matrix_data_t sq3x3_orig[9] = { 0,1,2,3,4,5,6,7,8 };
    const matrix_data_t sq3x3_transposed[9] = { 0,3,6,1,4,7,2,5,8};

    matrix_data_t sq4x4[16]= { 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 };/* 4x4 square, even length*/
    const matrix_data_t sq4x4_orig[16] = { 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 };
    const matrix_data_t sq4x4_transposed[16] = { 0,4,8,12,1,5,9,13,2,6,10,14,3,7,11,15 };

    /* 2x3 rectangle */
    const matrix_data_t r2x3_orig[6] = { 0,1,2,3,4,5 };
    const matrix_data_t r2x3_transposed[6] = { 0,3,1,4,2,5 };
    matrix_data_t r2x3_copy[6];

    matrix_data_t r2x3_2D[2][3] = { {0,1,2},{3,4,5} };  /* 2x3 2D rectangle */
    matrix_data_t r2x3_2D_t[3][2];

    /* matrix_data_t r3x2[6] = { 0,1,2,3,4,5 }; */
    matrix_data_t r3x2_copy[6];
    /* 3x2 rectangle */
    const matrix_data_t r3x2_orig[6] = { 0,1,2,3,4,5 };
    const matrix_data_t r3x2_transposed[6] = { 0,2,4,1,3,5 };

    matrix_data_t r6x1[6] = { 0,1,2,3,4,5 };    /* 6x1 */
    matrix_data_t r6x1_copy[6];

    matrix_data_t r1x1[1] = { 0 };  /*1x1*/
    matrix_data_t r1x1_copy[1];

    /* 3x3 tests, 2D array tests */
    transpose_inplace(sq3x3, 3);    /* transpose in place */
    assert(!test_cmp(sq3x3, sq3x3_transposed, 3, 3));
    transpose_inplace(sq3x3, 3);    /* transpose again */
    assert(!test_cmp(sq3x3, sq3x3_orig, 3, 3));

    transpose(sq3x3, sq3x3_cpy, 3, 3);  /* transpose copy 3x3*/
    assert(!test_cmp(sq3x3_cpy, sq3x3_transposed, 3, 3));

    transpose((matrix_data_t*)sq3x3_2D, (matrix_data_t*)sq3x3_2D_copy, 3, 3);   /* 2D array transpose/copy */
    assert(!test_cmp((matrix_data_t*)sq3x3_2D_copy, sq3x3_transposed, 3, 3));
    transpose_inplace((matrix_data_t*)sq3x3_2D_copy, 3);    /* 2D array transpose in place */
    assert(!test_cmp((matrix_data_t*)sq3x3_2D_copy, sq3x3_orig, 3, 3));

    /* 4x4 tests */
    transpose_inplace(sq4x4, 4);    /* transpose in place */
    assert(!test_cmp(sq4x4, sq4x4_transposed, 4,4));
    transpose_inplace(sq4x4, 4);    /* transpose again */
    assert(!test_cmp(sq4x4, sq4x4_orig, 3, 3));

    /* 2x3,3x2 tests */
    transpose(r2x3_orig, r2x3_copy, 2, 3);
    assert(!test_cmp(r2x3_copy, r2x3_transposed, 3, 2));

    transpose(r3x2_orig, r3x2_copy, 3, 2);
    assert(!test_cmp(r3x2_copy, r3x2_transposed, 2,3));

    /* 2D array */
    transpose((matrix_data_t*)r2x3_2D, (matrix_data_t*)r2x3_2D_t, 2, 3);
    assert(!test_cmp((matrix_data_t*)r2x3_2D_t, r2x3_transposed, 3,2));

    /* Nx1 test, 1x1 test */
    transpose(r6x1, r6x1_copy, 6, 1);
    assert(!test_cmp(r6x1_copy, r6x1, 1, 6));

    transpose(r1x1, r1x1_copy, 1, 1);
    assert(!test_cmp(r1x1_copy, r1x1, 1, 1));

}

void rotate_test() {

    /* 3x3 square */
    const matrix_data_t sq3x3[9] = { 0,1,2,3,4,5,6,7,8 };
    const matrix_data_t sq3x3_r90[9] = { 6,3,0,7,4,1,8,5,2 };
    const matrix_data_t sq3x3_180[9] = { 8,7,6,5,4,3,2,1,0 };
    const matrix_data_t sq3x3_l90[9] = { 2,5,8,1,4,7,0,3,6 };
    matrix_data_t sq3x3_copy[9];

    /* 3x3 square, 2D */
    matrix_data_t sq3x3_2D[3][3] = { { 0,1,2 },{ 3,4,5 },{ 6,7,8 } };

    /* 4x4, 2D */
    matrix_data_t sq4x4[4][4] = { { 0,1,2,3 },{ 4,5,6,7 },{ 8,9,10,11 },{ 12,13,14,15 } };
    matrix_data_t sq4x4_copy[4][4];
    const matrix_data_t sq4x4_r90[16] = { 12,8,4,0,13,9,5,1,14,10,6,2,15,11,7,3 };
    const matrix_data_t sq4x4_l90[16] = { 3,7,11,15,2,6,10,14,1,5,9,13,0,4,8,12 };
    const matrix_data_t sq4x4_180[16] = { 15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0 };

    matrix_data_t r6[6] = { 0,1,2,3,4,5 };  /* rectangle with area of 6 (1x6,2x3,3x2, or 6x1) */
    matrix_data_t r6_copy[6];
    const matrix_data_t r1x6_r90[6] = { 0,1,2,3,4,5 };
    const matrix_data_t r1x6_l90[6] = { 5,4,3,2,1,0 };
    const matrix_data_t r1x6_180[6] = { 5,4,3,2,1,0 };

    const matrix_data_t r2x3_r90[6] = { 3,0,4,1,5,2 };
    const matrix_data_t r2x3_l90[6] = { 2,5,1,4,0,3 };
    const matrix_data_t r2x3_180[6] = { 5,4,3,2,1,0 };

    const matrix_data_t r3x2_r90[6] = { 4,2,0,5,3,1 };
    const matrix_data_t r3x2_l90[6] = { 1,3,5,0,2,4 };
    const matrix_data_t r3x2_180[6] = { 5,4,3,2,1,0 };

    const matrix_data_t r6x1_r90[6] = { 5,4,3,2,1,0 };
    const matrix_data_t r6x1_l90[6] = { 0,1,2,3,4,5 };
    const matrix_data_t r6x1_180[6] = { 5,4,3,2,1,0 };

    /* sq3x3 tests */
    rotate(90, sq3x3, sq3x3_copy, 3, 3);    /* +90 */
    assert(!test_cmp(sq3x3_copy, sq3x3_r90, 3, 3));
    rotate(-90, sq3x3, sq3x3_copy, 3, 3);   /* -90 */
    assert(!test_cmp(sq3x3_copy, sq3x3_l90, 3, 3));
    rotate(180, sq3x3, sq3x3_copy, 3, 3);   /* 180 */
    assert(!test_cmp(sq3x3_copy, sq3x3_180, 3, 3));
    /* sq3x3 in-place rotations */
    memcpy( sq3x3_copy, sq3x3, 3 * 3 * sizeof(matrix_data_t));
    rotate_inplace(90, sq3x3_copy, 3);
    assert(!test_cmp(sq3x3_copy, sq3x3_r90, 3, 3));
    rotate_inplace(-90, sq3x3_copy, 3);
    assert(!test_cmp(sq3x3_copy, sq3x3, 3, 3)); /* back to 0 orientation */
    rotate_inplace(180, sq3x3_copy, 3);
    assert(!test_cmp(sq3x3_copy, sq3x3_180, 3, 3));
    rotate_inplace(-180, sq3x3_copy, 3);
    assert(!test_cmp(sq3x3_copy, sq3x3, 3, 3));
    rotate_inplace(180, (matrix_data_t*)sq3x3_2D, 3);/* 2D test */
    assert(!test_cmp((matrix_data_t*)sq3x3_2D, sq3x3_180, 3, 3));

    /* sq4x4 */
    rotate(90, (matrix_data_t*)sq4x4, (matrix_data_t*)sq4x4_copy, 4, 4);
    assert(!test_cmp((matrix_data_t*)sq4x4_copy, sq4x4_r90, 4, 4));
    rotate(-90, (matrix_data_t*)sq4x4, (matrix_data_t*)sq4x4_copy, 4, 4);
    assert(!test_cmp((matrix_data_t*)sq4x4_copy, sq4x4_l90, 4, 4));
    rotate(180, (matrix_data_t*)sq4x4, (matrix_data_t*)sq4x4_copy, 4, 4);
    assert(!test_cmp((matrix_data_t*)sq4x4_copy, sq4x4_180, 4, 4));

    /* r6 as 1x6 */
    rotate(90, r6, r6_copy, 1, 6);
    assert(!test_cmp(r6_copy, r1x6_r90, 1, 6));
    rotate(-90, r6, r6_copy, 1, 6);
    assert(!test_cmp(r6_copy, r1x6_l90, 1, 6));
    rotate(180, r6, r6_copy, 1, 6);
    assert(!test_cmp(r6_copy, r1x6_180, 1, 6));

    /* r6 as 2x3 */
    rotate(90, r6, r6_copy, 2, 3);
    assert(!test_cmp(r6_copy, r2x3_r90, 2, 3));
    rotate(-90, r6, r6_copy, 2, 3);
    assert(!test_cmp(r6_copy, r2x3_l90, 2, 3));
    rotate(180, r6, r6_copy, 2, 3);
    assert(!test_cmp(r6_copy, r2x3_180, 2, 3));

    /* r6 as 3x2 */
    rotate(90, r6, r6_copy, 3, 2);
    assert(!test_cmp(r6_copy, r3x2_r90, 3, 2));
    rotate(-90, r6, r6_copy, 3, 2);
    assert(!test_cmp(r6_copy, r3x2_l90, 3, 2));
    rotate(180, r6, r6_copy, 3, 2);
    assert(!test_cmp(r6_copy, r3x2_180, 3, 2));

    /* r6 as 6x1 */
    rotate(90, r6, r6_copy, 6, 1);
    assert(!test_cmp(r6_copy, r6x1_r90, 6, 1));
    rotate(-90, r6, r6_copy, 6, 1);
    assert(!test_cmp(r6_copy, r6x1_l90, 6, 1));
    rotate(180, r6, r6_copy, 6, 1);
    assert(!test_cmp(r6_copy, r6x1_180, 6, 1));
}

/* test comparison fn, return 0 on match else non zero */
int test_cmp(const matrix_data_t* lhs, const matrix_data_t* rhs, int rows, int cols) {

    int r, c;

    for (r = 0; r < rows; ++r) {
        for (c = 0; c < cols; ++c) {
            if ((lhs + r * cols)[c] != (rhs + r * cols)[c])
                return -1;
        }
    }
    return 0;
}

/*
Reverse values in place of each row in 2D matrix data[rows][cols] or in 1D pointer with logical rows/cols
[A B C] ->  [C B A]
[D E F]     [F E D]
*/
void reverse_rows(matrix_data_t* data, int rows, int cols) {

    int r, c;
    matrix_data_t temp;
    matrix_data_t* pRow = NULL;

    for (r = 0; r < rows; ++r) {
        pRow = (data + r * cols);
        for (c = 0; c < (int)(cols / 2); ++c) { /* explicit truncate */
            temp = pRow[c];
            pRow[c] = pRow[cols - 1 - c];
            pRow[cols - 1 - c] = temp;
        }
    }
}

/*
Reverse values in place of each column in 2D matrix data[rows][cols] or in 1D pointer with logical rows/cols
[A B C] ->  [D E F]
[D E F]     [A B C]
*/
void reverse_cols(matrix_data_t* data, int rows, int cols) {

    int r, c;
    matrix_data_t temp;
    matrix_data_t* pRowA = NULL;
    matrix_data_t* pRowB = NULL;

    for (c = 0; c < cols; ++c) {
        for (r = 0; r < (int)(rows / 2); ++r) { /* explicit truncate */
            pRowA = data + r * cols;
            pRowB = data + cols * (rows - 1 - r);
            temp = pRowA[c];
            pRowA[c] = pRowB[c];
            pRowB[c] = temp;
        }
    }
}

/* Transpose NxM matrix to MxN matrix in O(n) time */
void transpose(const matrix_data_t* src, matrix_data_t* dst, int N, int M) {

    int i;
    for (i = 0; i<N*M; ++i) dst[(i%M)*N + (i / M)] = src[i];    /* one-liner version */

    /*
    expanded version of one-liner:  calculate XY based on array index, then convert that to YX array index
    int i,j,x,y;
    for (i = 0; i < N*M; ++i) {
    x = i % M;
    y = (int)(i / M);
    j = x * N + y;
    dst[j] = src[i];
    }
    */

    /*
    nested for loop version
    using ptr arithmetic to get proper row/column
    this is really just dst[col][row]=src[row][col]

    int r, c;

    for (r = 0; r < rows; ++r) {
        for (c = 0; c < cols; ++c) {
            (dst + c * rows)[r] = (src + r * cols)[c];
        }
    }
    */
}

/*
Transpose NxN matrix in place
*/
void transpose_inplace(matrix_data_t* data, int N ) {

    int r, c;
    matrix_data_t temp;

    for (r = 0; r < N; ++r) {
        for (c = r; c < N; ++c) { /*start at column=row*/
                                    /* using ptr arithmetic to get proper row/column */
                                    /* this is really just
                                    temp=dst[col][row];
                                    dst[col][row]=src[row][col];
                                    src[row][col]=temp;
                                    */
            temp = (data + c * N)[r];
            (data + c * N)[r] = (data + r * N)[c];
            (data + r * N)[c] = temp;
        }
    }
}

/*
Rotate 1D or 2D src matrix to dst matrix in a direction (90,180,-90)
Precondition:  src and dst are 2d matrices with dimensions src[rows][cols] and dst[cols][rows] or 1D pointers with logical rows/cols
*/
void rotate(int direction, const matrix_data_t* src, matrix_data_t* dst, int rows, int cols) {

    switch (direction) {
    case -90:
        transpose(src, dst, rows, cols);
        reverse_cols(dst, cols, rows);
        break;
    case 90:
        transpose(src, dst, rows, cols);
        reverse_rows(dst, cols, rows);
        break;
    case 180:
    case -180:
        /* bit copy to dst, use in-place reversals */
        memcpy(dst, src, rows*cols*sizeof(matrix_data_t));
        reverse_cols(dst, cols, rows);
        reverse_rows(dst, cols, rows);
        break;
    }
}

/*
Rotate array in a direction.
Array must be NxN 2D or 1D array with logical rows/cols
Direction can be (90,180,-90,-180)
*/
void rotate_inplace( int direction, matrix_data_t* data, int n) {

    switch (direction) {
    case -90:
        transpose_inplace(data, n);
        reverse_cols(data, n, n);
        break;
    case 90:
        transpose_inplace(data, n);
        reverse_rows(data, n, n);
        break;
    case 180:
    case -180:
        reverse_cols(data, n, n);
        reverse_rows(data, n, n);
        break;
    }
}

`