C++ 如何将 N x N 矩阵旋转 90 度？

How to rotate a N x N matrix by 90 degrees?

提问by Passionate programmer

How to rotate a N x N matrix by 90 degrees. I want it to be inplace?

如何将 N x N 矩阵旋转 90 度。我希望它就位？

回答by Pavel Radzivilovsky

for(int i=0; i<n/2; i++)
   for(int j=0; j<(n+1)/2; j++)
       cyclic_roll(m[i][j], m[n-1-j][i], m[n-1-i][n-1-j], m[j][n-1-i]);


void cyclic_roll(int &a, int &b, int &c, int &d)
{
   int temp = a;
   a = b;
   b = c;
   c = d;
   d = temp;
}

NoteI haven't tested this, just compoosed now on the spot. Please test before doing anything with it.

请注意，我还没有对此进行测试，只是在现场进行了组合。请在对它进行任何操作之前进行测试。

回答by elliptic00

here is my solution: (rotate pi/2 clockwise)

这是我的解决方案：（顺时针旋转 pi/2）

1. do the transpose of the array, (like matrix transpose)

2. reverse the elements for each row

   cons int row = 10;
   cons int col = 10;
   //transpose
   for(int r = 0; r < row; r++) {
     for(int c = r; c < col; c++) {  
       swap(Array[r][c], Array[c][r]);
     }
   }
   //reverse elements on row order
   for(int r = 0; r < row; r++) {
       for(int c =0; c < col/2; c++) {
         swap(Array[r][c], Array[r][col-c-1])
       }
   }
   

1. 做数组的转置，（如矩阵转置）

2. 反转每一行的元素

   cons int row = 10;
   cons int col = 10;
   //transpose
   for(int r = 0; r < row; r++) {
     for(int c = r; c < col; c++) {  
       swap(Array[r][c], Array[c][r]);
     }
   }
   //reverse elements on row order
   for(int r = 0; r < row; r++) {
       for(int c =0; c < col/2; c++) {
         swap(Array[r][c], Array[r][col-c-1])
       }
   }
   

if rotate pi/2 in counter-clockwise

如果逆时针旋转 pi/2

1. transpose the array

2. reverse the elements on column order

1. 转置数组

2. 按列顺序反转元素

never test the code! any suggestion would be appreciated!

永远不要测试代码！任何建议将不胜感激！

回答by Chetan Narsude

A complete C program which illustrates my approach. Essentially it's recursive algo. At each recursion you rotate the outer layer. Stop when your matrix is 1x1 or 0x0.

一个完整的 C 程序，它说明了我的方法。本质上它是递归算法。在每次递归时，您都会旋转外层。当您的矩阵为 1x1 或 0x0 时停止。

#include <stdio.h>

int matrix[4][4] = {
     {11, 12, 13, 14},
     {21, 22, 23, 24},
     {31, 32, 33, 34},
     {41, 42, 43, 44} 
};

void print_matrix(int n)
{
   for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
         printf(" %d ", matrix[i][j]);
      }
      printf("\n");
   }
}

int *get(int offset, int x, int y)
{
   return &matrix[offset + x][offset + y];
}

void transpose(int offset, int n)
{
   if (n > 1) {
      for (int i = 0; i < n - 1; i++) {
         int *val1 = get(offset, 0, i);
         int *val2 = get(offset, i, n - 1);
         int *val3 = get(offset, n - 1, n - 1 - i);
         int *val4 = get(offset, n - 1 - i, 0);

         int temp = *val1;
         *val1 = *val4;
         *val4 = *val3;
         *val3 = *val2;
         *val2 = temp;
      }

      transpose(offset + 1, n - 2);
   }
}

main(int argc, char *argv[])
{
   print_matrix(4);
   transpose(0, 4);
   print_matrix(4);
   return 0;
}

回答by Jiaji Li

//Java version, fully tested

public class Rotate90degree {


        public static void reverseElementsRowWise(int[][] matrix) {
            int n = matrix.length;
            for(int i = 0; i < n; ++i) {
                for(int j = 0; j < n / 2; ++j) {
                    int temp = matrix[i][n - j - 1];
                    matrix[i][n - j - 1] = matrix[i][j];
                    matrix[i][j] = temp;
                }
            }
        }

        public static void transpose(int[][] matrix) {
            int n = matrix.length;
            for(int i = 0; i < n; ++i) {
                for(int j = i + 1; j < n; ++j) {
                    int temp = matrix[i][j];
                    matrix[i][j] = matrix[j][i];
                    matrix[j][i] = temp;
                }
            }
        }

        public static void rotate90(int[][] matrix) {
            transpose(matrix);
            reverseElementsRowWise(matrix);
        }

        public static void print(int[][] matrix) {
            int n = matrix.length;
            for(int i = 0; i < n; ++i) {
                for(int j = 0; j < n; ++j) {
                    System.out.print(matrix[i][j]);
                    System.out.print(' ');
                }
                System.out.println();
            }
        }

        public static void main(String[] args) {
            int[][] matrix = {
                    {1, 2, 3, 4},
                    {5, 6, 7, 8},
                    {9, 10, 11, 12},
                    {13, 14, 15, 16}};
            System.out.println("before");
            print(matrix);
            rotate90(matrix);
            System.out.println("after");
            print(matrix);
        }
}

回答by samoz

You could create a second array and then copy the first one into the second one by reading row-major in the first one and writing column-major to the second one.

您可以创建第二个数组，然后通过读取第一个数组中的行优先并将列优先写入第二个数组，将第一个数组复制到第二个数组中。

So you would copy:

所以你会复制：

1  2  3
4  5  6
7  8  9

and you would read the first row then write it back up starting like:

你会读第一行，然后把它写回来，像这样：

3
2
1