在 Java 中旋转 NxN 矩阵

Rotating a NxN matrix in Java

提问by JGY

This is a question from Cracking the Coding Interview. The solution says that the program rotates the exterior edges, then the interior edges. However, I'm having trouble following the logic of both the for loops.

这是一个来自 Cracking the Coding Interview 的问题。解决方案说程序先旋转外边缘，然后旋转内边缘。但是，我无法遵循两个 for 循环的逻辑。

Could somebody explain the logic of the code (e.g. why they do "layer < n/2" and the four steps of "left -> top" and "bottom -> left" etc)? On a side note, how would one's thought process be when coming up with this during a coding interview?

有人能解释一下代码的逻辑吗（例如，他们为什么要做“layer < n/2”和“left -> top”和“bottom -> left”等四个步骤）？附带说明一下，在编码面试中提出这个问题时，一个人的思维过程是怎样的？

Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees. Can you do this in place?

给定一个由 NxN 矩阵表示的图像，其中图像中的每个像素为 4 个字节，编写一个方法将图像旋转 90 度。你能在现场做到这一点吗？

public static void rotate(int[][] matrix, int n) {
    for (int layer = 0; layer < n / 2; ++layer) {
        int first = layer;
        int last = n - 1 - layer;
        for(int i = first; i < last; ++i) {
            int offset = i - first;
            int top = matrix[first][i]; // save top

            // left -> top
            matrix[first][i] = matrix[last-offset][first];          

            // bottom -> left
            matrix[last-offset][first] = matrix[last][last - offset]; 

            // right -> bottom
            matrix[last][last - offset] = matrix[i][last]; 

            // top -> right
            matrix[i][last] = top; // right <- saved top
        }
    }
}

回答by Jason

Overview

概述

Consider a sample matrix could look like this:

考虑一个示例矩阵可能如下所示：

ABCD
EFGH
IJKL
MNOP

For the purposes of my explanation, ABCD is considered as row 0, EFGH is row 1, and so on. The first pixel of row 0 is A.

为了我的解释，ABCD 被视为第 0 行，EFGH 被视为第 1 行，依此类推。第 0 行的第一个像素是 A。

Also, when I talk about the outer shell, I am referring to:

另外，当我谈到外壳时，我指的是：

ABCD
E  H
I  L
MNOP

First let's look at the code that moves the values.

首先让我们看看移动值的代码。

    int top = matrix[first][i]; // save top

The first line caches the value in the top position. This refers to the position on the top row of the matrix identified by [first][i]. Eg: saving the A.

第一行将值缓存在顶部位置。这是指由 [first][i] 标识的矩阵顶行上的位置。例如：保存A.

    // left -> top
    matrix[first][i] = matrix[last-offset][first];          

The next part moves the value from the left position into the top position. Eg: taking the Mand putting it where the Ais.

下一部分将值从左侧位置移动到顶部位置。例如：M把它放在那里A。

    // bottom -> left
    matrix[last-offset][first] = matrix[last][last - offset]; 

The next part moves the value from the bottom position into the left position. Eg: taking the Pand putting it where the Mis.

下一部分将值从底部位置移动到左侧位置。例如：P把它放在那里M。

    // right -> bottom
    matrix[last][last - offset] = matrix[i][last]; 

The next part moves the value from the right position into the bottom position. Eg: taking the Dand putting it where the Pis.

下一部分将值从正确位置移动到底部位置。例如：D把它放在那里P。

    // top -> right
    matrix[i][last] = top; // right <- saved top

The last part moves the value from the cache (what was the top position) into the right position. Eg: putting the Afrom the first step where the Dis.

最后一部分将值从缓存（顶部位置）移动到正确的位置。例如：将A第一步放在Dis 的位置。

Next the loops.

接下来是循环。

The outer loop runs from row 0 to half the total number of rows. This is because when you rotate row 0, it also rotates the last row and when you rotate row 1, it also rotates the second-to-last row, and so on.

外循环从第 0 行运行到总行数的一半。这是因为当您旋转第 0 行时，它也会旋转最后一行，当您旋转第 1 行时，它也会旋转倒数第二行，依此类推。

The inner loop runs from the first pixel position (or column) in the row to the last. Keep in mind that for row 0, this is from pixel 0 to the last pixel, but for row 1, this is from pixel 1 to the second-to-last pixel, since the first and last pixels are rotated as part of row 0.

内循环从行中的第一个像素位置（或列）运行到最后一个。请记住，对于第 0 行，这是从像素 0 到最后一个像素，但对于第 1 行，这是从像素 1 到倒数第二个像素，因为第一个和最后一个像素作为第 0 行的一部分旋转.

So the first iteration of the outer loop makes the outer shell rotate. In other words:

所以外循环的第一次迭代使外壳旋转。换句话说：

ABCD
EFGH
IJKL
MNOP

becomes:

变成：

MIEA
NFGB
OJKC
PLHD

See how the outer shell has rotated clockwise, but the inner core has not moved.

看看外壳如何顺时针旋转，但内核没有移动。

Then the second iteration of the outer loop causes the second row to rotate (excluding the first and last pixels) and we end up with:

然后外循环的第二次迭代导致第二行旋转（不包括第一个和最后一个像素），我们最终得到：

MIEA
NJFB
OKGC
PLHD

回答by Saurabh Patil

I'm writing this answer because even after reading the answer posted by Jason above (it's nice and did resolve a couple of questions I had) it still wasn't clear to me what role is variable "offset" playing in this logic, so spending a couple of hours to understand this I thought to share it with everyone.

我写这个答案是因为即使在阅读了上面 Jason 发布的答案之后（这很好并且确实解决了我的几个问题）我仍然不清楚变量“偏移”在这个逻辑中扮演什么角色，所以花了几个小时来理解这一点，我想与大家分享。

There are many variables used here and it's important to understand the significance of each one.

这里使用了许多变量，了解每个变量的意义很重要。

If you look at the variable 'first', it's useless, it's essentially the 'layer' itself, 'first' isn't modified at all in the whole logic. So I have removed 'first' variable (and it works, read ahead).

如果你看变量'first'，它是没用的，它本质上是'layer'本身，'first'在整个逻辑中根本没有被修改。所以我删除了“第一个”变量（它有效，请提前阅读）。

To understand how each of these values change in every iteration of the inner for loop I have printed the values of these variables. Take a look at the output and understand which values change when we move from one corner to another in the inner for loop, which values stay constant while traversing a single layer and which values change only when we change the layer.

为了了解这些值在内部 for 循环的每次迭代中如何变化，我打印了这些变量的值。查看输出并了解当我们在内部 for 循环中从一个角落移动到另一个角落时哪些值会发生变化，哪些值在遍历单个图层时保持不变，哪些值仅在我们更改图层时发生变化。

One iteration of inner loop moves one single block. Number of iterations needed to move a single layer will change as we go inwards. The variable 'last' does that job for us, it restricts the inner loop (restricts the inner layer & stops us from going beyond the shell, building upon the nomenclature Jason used)

内循环的一次迭代移动一个单独的块。随着我们向内移动，移动单个层所需的迭代次数会发生变化。变量“last”为我们完成了这项工作，它限制了内部循环（限制内层并阻止我们超越外壳，建立在 Jason 使用的命名法之上）

Time to study the output.

是时候研究输出了。

I have used 6x6 matrix.

我使用了 6x6 矩阵。

Input: 

 315 301 755 542 955 33
 943 613 233 880 945 280
 908 609 504 61 849 551
 933 251 706 707 913 917
 479 785 634 97 851 745
 472 348 104 645 17 273

--------------Starting an iteration of OUTER FOR LOOP------------------

--------------Starting an iteration of inner for loop------------------
layer =0
last =5
i =0
buffer = 315
offset = i-layer = 0
Current Status: 

 472 301 755 542 955 315
 943 613 233 880 945 280
 908 609 504 61 849 551
 933 251 706 707 913 917
 479 785 634 97 851 745
 273 348 104 645 17 33
--------------Finished an iteration of inner for loop------------------

--------------Starting an iteration of inner for loop------------------
layer =0
last =5
i =1
buffer = 301
offset = i-layer = 1
Current Status: 

 472 479 755 542 955 315
 943 613 233 880 945 301
 908 609 504 61 849 551
 933 251 706 707 913 917
 17 785 634 97 851 745
 273 348 104 645 280 33
--------------Finished an iteration of inner for loop------------------

--------------Starting an iteration of inner for loop------------------
layer =0
last =5
i =2
buffer = 755
offset = i-layer = 2
Current Status: 

 472 479 933 542 955 315
 943 613 233 880 945 301
 908 609 504 61 849 755
 645 251 706 707 913 917
 17 785 634 97 851 745
 273 348 104 551 280 33
--------------Finished an iteration of inner for loop------------------

--------------Starting an iteration of inner for loop------------------
layer =0
last =5
i =3
buffer = 542
offset = i-layer = 3
Current Status: 

 472 479 933 908 955 315
 943 613 233 880 945 301
 104 609 504 61 849 755
 645 251 706 707 913 542
 17 785 634 97 851 745
 273 348 917 551 280 33
--------------Finished an iteration of inner for loop------------------

--------------Starting an iteration of inner for loop------------------
layer =0
last =5
i =4
buffer = 955
offset = i-layer = 4
Current Status: 

 472 479 933 908 943 315
 348 613 233 880 945 301
 104 609 504 61 849 755
 645 251 706 707 913 542
 17 785 634 97 851 955
 273 745 917 551 280 33
--------------Finished an iteration of inner for loop------------------
--------------Finished an iteration of OUTER FOR LOOP------------------

--------------Starting an iteration of OUTER FOR LOOP------------------

--------------Starting an iteration of inner for loop------------------
layer =1
last =4
i =1
buffer = 613
offset = i-layer = 0
Current Status: 

 472 479 933 908 943 315
 348 785 233 880 613 301
 104 609 504 61 849 755
 645 251 706 707 913 542
 17 851 634 97 945 955
 273 745 917 551 280 33
--------------Finished an iteration of inner for loop------------------

--------------Starting an iteration of inner for loop------------------
layer =1
last =4
i =2
buffer = 233
offset = i-layer = 1
Current Status: 

 472 479 933 908 943 315
 348 785 251 880 613 301
 104 609 504 61 233 755
 645 97 706 707 913 542
 17 851 634 849 945 955
 273 745 917 551 280 33
--------------Finished an iteration of inner for loop------------------

--------------Starting an iteration of inner for loop------------------
layer =1
last =4
i =3
buffer = 880
offset = i-layer = 2
Current Status: 

 472 479 933 908 943 315
 348 785 251 609 613 301
 104 634 504 61 233 755
 645 97 706 707 880 542
 17 851 913 849 945 955
 273 745 917 551 280 33
--------------Finished an iteration of inner for loop------------------
--------------Finished an iteration of OUTER FOR LOOP------------------

--------------Starting an iteration of OUTER FOR LOOP------------------

--------------Starting an iteration of inner for loop------------------
layer =2
last =3
i =2
buffer = 504
offset = i-layer = 0
Current Status: 

 472 479 933 908 943 315
 348 785 251 609 613 301
 104 634 706 504 233 755
 645 97 707 61 880 542
 17 851 913 849 945 955
 273 745 917 551 280 33
--------------Finished an iteration of inner for loop------------------
--------------Finished an iteration of OUTER FOR LOOP------------------

 472 479 933 908 943 315
 348 785 251 609 613 301
 104 634 706 504 233 755
 645 97 707 61 880 542
 17 851 913 849 945 955
 273 745 917 551 280 33

Sorry but there is no way other than to ponder upon how the values of layer, i and offset change to understand what the heck is happening here.

抱歉，除了思考 layer、i 和 offset 的值如何变化以了解这里发生的事情之外别无他法。

Finally the code

最后是代码

Here is the code where I removed unnecessary first and added all the print statements, in case if anyone wants to play more. This code also has random matrix initialization and printing:

这是我首先删除不必要的代码并添加了所有打印语句的代码，以防万一有人想玩更多。此代码还具有随机矩阵初始化和打印：

package com.crackingthecodinginterview.assignments.chap1;

public class Problem6RotateMatrix90 {

    public static void main(String args[]){
        int[][] matrix = new int[6][6];
        initializeMatrix(matrix,6);
        System.out.println("Input: ");
        printMatrix(matrix,6);
        rotate(matrix,6);
        printMatrix(matrix,6);
    }

    public static void rotate(int[][] matrix, int n) {
        for (int layer = 0; layer < n / 2; ++layer) {
            System.out.println("\n--------------Starting an iteration of OUTER FOR LOOP------------------");

            int last = n - 1 - layer;
            for(int i = layer; i < last; ++i) {
                int offset = i - layer;
                int buffer = matrix[layer][i]; // save top
                System.out.println("\n--------------Starting an iteration of inner for loop------------------");
                System.out.println("layer ="+layer);

                System.out.println("last ="+last);
                System.out.println("i ="+i);

                System.out.println("buffer = "+buffer);
                System.out.println("offset = i-layer = "+ offset);

                // left -> top
                matrix[layer][i] = matrix[last-offset][layer];          

                // bottom -> left
                matrix[last-offset][layer] = matrix[last][last - offset]; 

                // right -> bottom
                matrix[last][last - offset] = matrix[i][last]; 

                // top -> right
                matrix[i][last] = buffer; // right <- saved top

                //print
                System.out.println("Current Status: ");
                printMatrix(matrix,6);
                System.out.println("--------------Finished an iteration of inner for loop------------------");
            }
            System.out.println("--------------Finished an iteration of OUTER FOR LOOP------------------");

        }
    }

    public static void printMatrix(int[][] matrix,int n){
        System.out.print("\n");
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                System.out.print(" "+matrix[i][j]);
            }
            System.out.print("\n");
        }
    }

    public static void initializeMatrix(int[][] matrix,int n){
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                matrix[i][j]=(int) (Math.random() * 1000);
            }
        }
    }

}

回答by Lau Chok Sheak

Just saw that there is a simpler way to write the code by refactoring "last - offset":

刚刚看到有一种更简单的方式来通过重构“last-offset”来编写代码：

  public static void rotateInPlace90DegreesClockwise(int[][] matrix) {
      int n = matrix.length;
      int half = n / 2;

      for (int layer = 0; layer < half; layer++) {
          int first = layer;
          int last = n - 1 - layer;

          for (int i = first; i < last; i++) {
              int offset = i - first;
              int j = last - offset;
              int top = matrix[first][i]; // save top

              // left -> top
              matrix[first][i] = matrix[j][first];          

              // bottom -> left
              matrix[j][first] = matrix[last][j]; 

              // right -> bottom
              matrix[last][j] = matrix[i][last]; 

              // top -> right
              matrix[i][last] = top; // right <- saved top
          }
      }
  }

回答by Andrew B.

check this solution to do it in place.

检查此解决方案以执行到位。

public void rotateMatrix(Pixel[][] matrix) {

    for (int i = 0; i < matrix.length / 2; i++) {

        for (int j = 0; j < matrix.length - 1 - 2 * i; j++) {
            Pixel tmp = matrix[j + i][matrix.length - 1 - i];
            matrix[j + i][matrix.length - 1 - i] = matrix[i][j + i];
            matrix[i][j + i] = matrix[matrix.length - 1 - j - i][i];
            matrix[matrix.length - 1 - j - i][i] = matrix[matrix.length - 1 - i][matrix.length - 1 - j - i];
            matrix[matrix.length - 1 - i][matrix.length - 1 - j - i] = tmp;
        }
    }
}

回答by George Kagan

Here's my solution in JavaScript, it swaps values between a row and a column starting from the top-right edge, going inwards until the bottom-leftmost pair is swapped.

这是我在 JavaScript 中的解决方案，它从右上角开始，向内交换行和列之间的值，直到交换最左下角的一对。

function rotateMatrix(arr) {
    var n = arr.length - 1;

    for (var i = 0; i < n; i++) {
        for (var j = 0; j < n - i; j++) {
            var temp = arr[i][j];

            arr[i][j] = arr[n - j][n - i]; // top row
            arr[n - j][n - i] = temp; // right column
        }
    }

    return arr;
}

回答by Dyndrilliac

Yes, that code is pretty ugly and hard to read - primarily because the author didn't use very descriptive variable names. I solved that same problem using the same principles (treating the square matrix as a set of concentric squares and then rotating one at a time going from the outer square to the inner square). Here is my solution and the explanation of my thought process.

是的，该代码非常丑陋且难以阅读 - 主要是因为作者没有使用非常具有描述性的变量名称。我使用相同的原则解决了同样的问题（将方阵视为一组同心正方形，然后从外部正方形到内部正方形一次旋转一个）。这是我的解决方案和我的思考过程的解释。

The Code

代码

I used C#, but the syntax is nearly identical to Java. After copy/pasting, just change a.Lengthto a.lengthand it should be syntactically correct Java.

我使用 C#，但语法几乎与 Java 相同。复制/粘贴后，只需更改a.Length为a.length语法正确的 Java。

void swap(int[][] a, int g, int h, int i, int j) {
    int temp = a[g][h];
    a[g][h] = a[i][j];
    a[i][j] = temp;
}

int[][] rotateImage(int[][] a) {
    if (a.Length > 1) {
        int topRow = 0, bottomRow = a.Length - 1, leftCol = topRow, rightCol = bottomRow;

        while (topRow < bottomRow && leftCol < rightCol) {
            swap(a, topRow, leftCol, topRow, rightCol);
            swap(a, topRow, leftCol, bottomRow, leftCol);
            swap(a, bottomRow, leftCol, bottomRow, rightCol);

            for (int i = topRow + 1, j = bottomRow - 1; i < bottomRow && j > topRow; i++, j--) {
                swap(a, topRow, i, i, rightCol);
                swap(a, topRow, i, bottomRow, j);
                swap(a, topRow, i, j, leftCol);
            }

            topRow++; leftCol++;
            bottomRow--; rightCol--;
        }
    }

    return a;
}

You may notice that I could potentially get rid of the variables leftColand rightColsince they are kept equal to topRowand bottomRowrespectfully. The reason that I don't is because I feel it makes the code easier to follow.

您可能会注意到我可能会摆脱变量leftCol，rightCol因为它们保持平等topRow和bottomRow尊重。我不这样做的原因是因为我觉得它使代码更易于遵循。

The Explanation

说明

First, note that if given a 1x1matrix, we return the original matrix because there is only one pixel which means no rotation is necessary.

首先，请注意，如果给定一个1x1矩阵，我们将返回原始矩阵，因为只有一个像素，这意味着不需要旋转。

Next, imagine we are given the following 2x2matrix:

接下来，假设我们有以下2x2矩阵：

1 2
3 4

You could rotate this matrix in three swaps. Top Left -> Top Right, Top Left -> Bottom Left, and Top Left -> Bottom Right.

你可以在三个交换中旋转这个矩阵。Top Left -> Top Right、Top Left -> Bottom Left、 和Top Left -> Bottom Right。

4 1
2 3

Now imagine we are given the following 3x3matrix:

现在假设我们得到以下3x3矩阵：

1 2 3
4 5 6
7 8 9

Note that the inner square is our old friend the 1x1matrix. It's important to realize that all square matrices where n > 1 && n % 2 != 0will eventually reduce down to a 1x1in the center. Similarly, those where n > 1 && n % 2 == 0will reduce down to a 2x2in the center. We can handle both cases the same way.

请注意，内部正方形是我们的老朋友1x1矩阵。重要的是要意识到所有的方阵n > 1 && n % 2 != 0最终都会减少到1x1中心的 a。同样，那些 wheren > 1 && n % 2 == 0将减少到2x2中心。我们可以以相同的方式处理这两种情况。

Again, we will start with the corners of the outer square. We use our familiar previous three swaps: Top Left -> Top Right, Top Left -> Bottom Left, and Top Left -> Bottom Right.

同样，我们将从外部正方形的角开始。我们用我们熟悉的前三个互换：Top Left -> Top Right，Top Left -> Bottom Left，和Top Left -> Bottom Right。

7 2 1
4 5 6
9 8 3

Notice that the matrix is almost rotated; it's just those four pesky values in the centers of the exterior sides. But, also notice that each of those values are just one position away from the corners we rotated. If we continue our pattern of using a fixed starting point for our swaps the same way we did the corners, we could rotate the last four values like so: Top Middle -> Right Middle, Top Middle -> Bottom Middle, and Top Middle -> Left Middle. In terms of indices, "Top Middle" is just "Top Left" plus one. Similarly, "Right Middle" is just "Top Right" plus one. For some of the indices, it makes sense to start at the extreme large index (n - 1) and decrement. I refer to the smaller middle index as iand the larger middle index as j.

请注意，矩阵几乎旋转了；这只是外侧中心的那四个讨厌的值。但是，还要注意这些值中的每一个都离我们旋转的角只有一个位置。如果我们继续使用固定的起点为我们交换我们做的角落的方式相同的方式，我们可以旋转，像这样的最后四个值：Top Middle -> Right Middle，Top Middle -> Bottom Middle，和Top Middle -> Left Middle。在指数方面，“中上”只是“左上”加一。同样，“右中”就是“右上”加一。对于某些索引，从极大的索引 ( n - 1) 开始并递减是有意义的。我将较小的中间索引称为i，将较大的中间索引称为j。

7 4 1
8 5 2
9 6 3

It takes three swaps to rotate a 2x2matrix, six swaps to rotate a 3x3matrix, and in general it takes n!swaps to rotate a nxnmatrix. My whileloop rotates the corners for each concentric square in the matrix (and each square is smaller than the previous square), and then my forloop takes care of the values in-between the corners along the edges. It continues like this until either there are no more interior squares to rotate, or the only interior square remaining is a 1x1matrix.

旋转2x2矩阵需要 3 次交换，旋转矩阵需要 6 次交换3x3，通常需要n!交换才能旋转nxn矩阵。我的while循环旋转矩阵中每个同心正方形的角（每个正方形都小于前一个正方形），然后我的for循环处理沿边缘的角之间的值。如此继续直到没有更多的内部正方形要旋转，或者唯一剩余的内部正方形是一个1x1矩阵。

回答by VAT

Here's the solution in C#. Every N x Nmatrix will have floor (N/2)square cycles.

这是 C# 中的解决方案。每个N x N矩阵都有地板(N/2)平方循环。

For e.g. - Both 4×4& 5×5will have 2 rotatable layers.

对于如-两个4×4＆5×5将有2层的旋转。

Following corner-combination identifies the positions:

以下角组合标识位置：

(top,left) points to (first,first) --> 0,0
(top,right) points to (first,last) --> 0,n
(bottom,left) points to (last,first) --> n,0
(bottom,right) points to (last,last) --> n,n

Here's the code to rotate matrix by 90 degrees:

这是将矩阵旋转 90 度的代码：

    public static void RotateMatrixBy90Degress(int[][] matrix)
    {
        int matrixLen = matrix.Length;
        for (int layer = 0; layer < matrixLen / 2; layer++)
        {
            int first = layer;
            int last = matrixLen - first - 1;

            for (int i = first; i < last; i++)
            {
                int offset = i - first;
                int lastMinusOffset = last - offset;
                // store variable in a temporary variable
                int top = matrix[first][i];

                // move values from left --> top
                matrix[first][i] = matrix[lastMinusOffset][first];

                // move values from bottom --> left
                matrix[lastMinusOffset][first] = matrix[last][lastMinusOffset];

                // move values from right --> bottom
                matrix[last][lastMinusOffset] = matrix[i][last];

                // move values from top  --> right

                matrix[i][last] = top;
            }
        }
    }

Here's the code to generate random numbers in a matrix.

这是在矩阵中生成随机数的代码。

    public static void RotateMatrixImplementation(int len)
    {
        int[][] matrix = new int[len][];
        var random = new Random();
        for (int i = 0; i < matrix.Length; i++)
        {
            matrix[i] = new int[len]; // Create inner array
            for (int j = 0; j < matrix[i].Length; j++)
            {
                //generate random numbers
                matrix[i][j] = random.Next(1, Convert.ToInt32(Math.Pow(len, 3)));
            }
        }
        RotateMatrixBy90Degress(matrix);
    }

回答by Amrit Malla

Here's my 100% result submission to this problem

这是我对这个问题的 100% 结果提交

Firstly I've broken the 2D arraylist into 1D arrayList layerwise, Then rotated 1D matrix then again placed into matrix form While breaking 2D arraylist into 1D arrayList I've saved the positions of element in array so that we can place that rotated matrix at that position

首先，我已将 2D arraylist 逐层分解为 1D arrayList，然后旋转 1D 矩阵，然后再次放入矩阵形式同时将 2D arraylist 分解为 1D arrayList 我已经保存了元素在数组中的位置，以便我们可以将旋转矩阵放在那里位置

    import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

public class Solution {
        static List<Integer[]> storePosition = new ArrayList<>();

    public static ArrayList<Integer> rotateOneDArray(List<Integer> arr, int K) {
        int[] A = arr.stream().mapToInt(i -> i).toArray();
        // write your code in Java SE 8

        int r = K % (A.length);
        int[] ans = new int[A.length];
        int y;
        for (int i = 0; i < A.length; i++) {
            y = i - r;
            if (y < 0) {
                y += A.length;
            }
            ans[y] = A[i];
        }

        return (ArrayList<Integer>) Arrays.stream(ans).boxed().collect(Collectors.toList());

    }

    static ArrayList<ArrayList<Integer>> getLinearMatrix(List<List<Integer>> matrix) {
        ArrayList<ArrayList<Integer>> linear = new ArrayList<ArrayList<Integer>>();
        int M = matrix.get(0).size();
        int N = matrix.size();
        int m = M, n = N, i, j, counter = 0;
        Integer[] pos = new Integer[2];
        while (m >= 2 && n >= 2) {
            i = counter;
            j = counter;

            ArrayList<Integer> list = new ArrayList<>((m + n - 2) * 2);

            while (j < M - counter) {
                list.add(matrix.get(i).get(j));
                pos = new Integer[2];
                pos[0] = i;
                pos[1] = j;
                storePosition.add(pos);
                ++j;
            }
            --j;
            ++i;

            while (i < N - counter) {
                list.add(matrix.get(i).get(j));
                pos = new Integer[2];
                pos[0] = i;
                pos[1] = j;
                storePosition.add(pos);
                ++i;
            }
            --i;
            --j;
            while (j >= counter) {
                list.add(matrix.get(i).get(j));
                pos = new Integer[2];
                pos[0] = i;
                pos[1] = j;
                storePosition.add(pos);
                --j;
            }
            ++j;
            --i;
            while (i > counter) {
                list.add(matrix.get(i).get(j));
                pos = new Integer[2];
                pos[0] = i;
                pos[1] = j;
                storePosition.add(pos);
                --i;
            }
            linear.add(list);

            ++counter;
            m -= 2;
            n -= 2;
        }
        return linear;

    }


    // Complete the matrixRotation function below.
    static void matrixRotation(List<List<Integer>> matrix, int r) {

        int m = matrix.get(0).size();
        int n = matrix.size();

        ArrayList<ArrayList<Integer>> linearMat = getLinearMatrix(matrix);
        ArrayList<ArrayList<Integer>> rotatedLinearMat = new ArrayList<ArrayList<Integer>>();

        for (int f = 0; f < linearMat.size(); f++) {

            rotatedLinearMat.add(f, rotateOneDArray(linearMat.get(f), r));
        }

        int p = 0;

        Integer[][] result = new Integer[n][m];
        for (int i = 0; i < rotatedLinearMat.size(); ++i) {
            for (int j = 0; j < rotatedLinearMat.get(i).size(); ++j) {
                result[storePosition.get(p)[0]][storePosition.get(p)[1]] = rotatedLinearMat.get(i).get(j);
                ++p;
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                System.out.print(result[i][j] + " ");
            }
            System.out.println();
        }

    }

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

        String[] mnr = bufferedReader.readLine().replaceAll("\s+$", "").split(" ");

        int m = Integer.parseInt(mnr[0]);

        int n = Integer.parseInt(mnr[1]);

        int r = Integer.parseInt(mnr[2]);

        List<List<Integer>> matrix = new ArrayList<>();

        IntStream.range(0, m).forEach(i -> {
            try {
                matrix.add(
                    Stream.of(bufferedReader.readLine().replaceAll("\s+$", "").split(" "))
                        .map(Integer::parseInt)
                        .collect(toList())
                );
            } catch (IOException ex) {
                throw new RuntimeException(ex);
            }
        });

        matrixRotation(matrix, r);

        bufferedReader.close();
    }
}

回答by CodeNinja

Here is a simple solution that works perfectly for me.

这是一个非常适合我的简单解决方案。

 private int[][] rotateMatrix(int[][] matrix)
    {
        for(int i=0;i<matrix.length-1;i++)
        {
            for(int j =i;j<matrix[0].length;j++)
            {
                if(i!=j) {
                    int temp = matrix[i][j];
                    matrix[i][j] = matrix[j][i];
                    matrix[j][i] = temp;
                }
            }
        }
        return matrix;
    }

回答by user3743369

  /**
 * @param args
 */
public static void main(String[] args) {
    int n = 5; //5x5 matrix
    int[][] matrixInitial = initMatrix(n);
    int[][] matrixFinal = rotate(matrixInitial, n);
    System.out.println(matrixFinal.length);

    int m = 4; //4x4 matrix
    int[][] matrixInitial2 = initMatrix(m);
    int[][] matrixFinal2 = rotate(matrixInitial2, m);
    System.out.println(matrixFinal2.length);
}

private static int[][] rotate(int[][] matrixInitial, int n) {
//it is much like square layers. each layer will be read and rotated
    int layerCount = (n + 1) / 2; 
    System.out.println("n: " + n + " layerCount: " + layerCount);
    int[][] matrixFinal = new int[n][n];
    if (n % 2 == 1) { // for odd # layers the centre does not move
        matrixFinal[n / 2][n / 2] = matrixInitial[n / 2][n / 2];
        layerCount -= 1;
    }

    for (int i = 0; i < layerCount; i++) {
        int width = n - (2 * i); // width of the layer
        System.out.println("width: " + width);
        int[] top = new int[width]; // read top
        for (int j = 0; j < width; j++) {
            top[j] = matrixInitial[i][i + j];
        }
        System.out.println("top: " + Arrays.toString(top));

        //OK TOP TO RIGHT

        for (int j = 0; j < width; j++) { // move top to right 
            matrixFinal[j+i][width-1+i] = top[j];
        }

        int[] tempLeft = new int[width]; // left will be read backwards
        for (int j = 0; j < width; j++) { // reverse the temp
            tempLeft[j] = matrixInitial[i + j][i];
        }

        int[] left = new int[width];
        int indexTemp = 0;
        for (int j = width-1; j >= 0; j--) { // move temp to left
            left[indexTemp++] = tempLeft[j];
        }
        System.out.println("left: " + Arrays.toString(left));

        //OK LEFT TO TOP

        for (int j = 0; j < width; j++) { // move left to top
            matrixFinal[i][j + i] = left[j];
        }

        int[] bottom = new int[width]; read bottom
        for (int j = 0; j < width; j++) {
            bottom[j] = matrixInitial[width - 1 + i][j + i];
        }
        System.out.println("bottom: " + Arrays.toString(bottom));

        //OK BOTTOM TO LEFT

        for (int j = 0; j < width; j++) { // move bottom to left
            matrixFinal[j+i][i] = bottom[j];
        }

        int[] tempRight = new int[width]; // right will be read backwards
        for (int j = 0; j < width; j++) {
            tempRight[j] = matrixInitial[j + i][width - 1 + i];
        }
        int[] right = new int[width]; //reverse the temp
        int indexTemp2 = 0;
        for (int j = width; j > 0; j--) {
            right[indexTemp2++] = tempRight[j - 1];
        }
        System.out.println("right: " + Arrays.toString(right));

        //OK RIGHT TO BOTTOM
        for (int j = 0; j < width; j++) { // move right to bottom
            matrixFinal[width-1+i][j + i] = right[j];
        }

    }
    for (int i = 0; i < n; i++) {
        System.out.println(Arrays.toString(matrixFinal[i]));
    }
    return matrixFinal;
}

private static int[][] initMatrix(int n) { // init the matrix
    int[][] matrix = new int[n][n];
    int fill = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            matrix[i][j] = fill++;
        }
    }

    for (int i = 0; i < n; i++) {
        System.out.println(Arrays.toString(matrix[i]));
    }
    System.out.println("******");
    return matrix;
}