在Java中旋转一个NxN矩阵

Question

在Java中旋转一个NxN矩阵

30

这是一个来自《Cracking the Coding Interview》的问题。解决方案表示程序先旋转外部边缘，然后旋转内部边缘。然而，我很难理解两个for循环的逻辑。有人能解释一下代码的逻辑吗（例如为什么要执行“layer < n/2”以及“左侧->上侧”和“底部->左侧”等四个步骤）？另外，如果在编程面试中想出这个方法，思考过程会是怎样的？

给定一个由N×N矩阵表示的图像，其中图像中的每个像素占用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
        }
    }
}

- JGY

11个回答

6

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

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

如果你看一下变量“first”，它是无用的，实际上它就是“层”本身，“first”在整个逻辑中根本没有被修改。因此，我已经删除了变量“first”（它依然有效，请继续阅读）。

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

内部循环的一次迭代移动一个单独的块。移动单个层所需的迭代次数将随着向内部前进而改变。变量“last”为我们完成了这项工作，它限制了内部循环（限制内部层并阻止我们超出外壳，建立在Jason命名法的基础上）

是时候研究输出了。

我使用了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

很抱歉，除了仔细思考层级、i和偏移值的变化以理解此处发生的事情外没有其他方法。

最后附上代码

以下是代码，在去掉不必要的首行并添加所有print语句的基础上，如果有人想进行更多尝试，这段代码还具有随机矩阵初始化和打印功能：

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);
            }
        }
    }

}

- Saurabh Patil

2

检查这个解决方案，使其能够原地操作。

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;
        }
    }
}

- Andrew B.

2

刚刚看到了一种更简便的代码编写方式，可以通过重构“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
        }
    }
}

- Lau Chok Sheak

1

你能解释一下吗？这个逻辑是什么？ - Saurabh Patil

0

在这段代码中，您可以将NxN矩阵旋转多次，并且可以选择方向1表示顺时针，-1表示相反方向。在rotateMatrix方法中，您需要使用for-for循环来处理每个角落。

公共类JavaApplication144 {

public static void main(String[] args) {
    Scanner s = new Scanner(System.in);
    int matrix[][] = {{56, 12, 8, 90, 40}, {87, 76, 99, 1, 32}, {34, 43, 25, 78, 6}, {39, 555, 65, 88, 3}, {44, 75, 77, 14, 10}};
    print();
}

这是方法：

static int[][] shiftingmatris(int[][] p_matris, int dırectıon) {
    int[][] tempmatris = new int[p_matris.length][p_matris[0].length];

    if (dırectıon == -1) {
        for (int i = 0; i < p_matris.length; i++) {
            for (int j = 0; j < p_matris[0].length; j++) {
                if (i == 0 && j != p_matris[0].length - 1) {
                    tempmatris[i][j + 1] = p_matris[i][j];
                } else if (i == p_matris.length - 1 && j != 0) {
                    tempmatris[i][j - 1] = p_matris[i][j];
                }
            }
        }
        for (int i = 0; i < p_matris.length; i++) {
            for (int j = 0; j < p_matris[0].length; j++) {
                if (j == 0 && i != 0) {
                    tempmatris[i - 1][j] = p_matris[i][j];
                } else if (j == p_matris[1].length - 1 && i != p_matris.length - 1) {
                    tempmatris[i + 1][j] = p_matris[i][j];

                }
            }
        }

    } else if (dırectıon == 1) {
        for (int i = 0; i < p_matris.length; i++) {
            for (int j = 0; j < p_matris[1].length; j++) {
                if (i == 0 && j != 0) {
                    tempmatris[i][j - 1] = p_matris[i][j];

                } else if (i == p_matris.length - 1 && j != p_matris[0].length - 1) {
                    tempmatris[i][j + 1] = p_matris[i][j];
                }
            }
        }
        for (int i = 0; i < p_matris.length; i++) {
            for (int j = 0; j < p_matris[0].length; j++) {
                if (j == 0 && i != p_matris.length - 1) {
                    tempmatris[i + 1][j] = p_matris[i][j];
                } else if (j == p_matris[0].length - 1 && i != 0) {
                    tempmatris[i - 1][j] = p_matris[i][j];

                }
            }
        }

    }

    for (int i = 1; i < p_matris.length - 1; i++) {
        for (int j = 1; j < p_matris[1].length - 1; j++) {
            tempmatris[i][j] = p_matris[i][j];
        }
    }
    return tempmatris;
}

}

你还需要打印矩阵。可以通过以下方法实现：

public static void print(){
 Scanner s = new Scanner(System.in);
    System.out.println("times of rotate: ");
    int dondurme = s.nextInt();
    System.out.println("direction?");
    int dırectıon = s.nextInt();
    int matrix[][] = {{56, 12, 8, 90, 40}, {87, 76, 99, 1, 32}, {34, 43, 25, 78, 6}, {39, 555, 65, 88, 3}, {44, 75, 77, 14, 10}};
    System.out.println(" ");
    for (int i = 0; i < matrix.length; i++) {
        System.out.println(" ");
        for (int j = 0; j < matrix.length; j++) {
            System.out.print(" ");
            System.out.print(matrix[i][j] + " ");
        }
    }

    for (int i = 0; i < dondurme; i++) {
        matrix = shiftingmatris(matrix, dırectıon);
    }
    System.out.println(" ");
    for (int i = 0; i < matrix.length; i++) {
        System.out.println(" ");
        for (int j = 0; j < matrix.length; j++) {
            System.out.print(" ");
            System.out.print(matrix[i][j] + " ");
        }
    }
}

- melikekecelioglu

0

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

代码

我使用了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;
}

你可能会注意到，我有可能可以摆脱变量leftCol和rightCol，因为它们都等于topRow和bottomRow。我不这样做的原因是我觉得这样可以使代码更容易理解。

解释

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

接下来，想象一下我们得到以下2x2矩阵：

1 2
3 4

你可以通过三次交换来旋转这个矩阵。左上 -> 右上，左上 -> 左下 和 左上 -> 右下。

4 1
2 3

现在想象一下，我们有一个给定的3x3矩阵：

1 2 3
4 5 6
7 8 9

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

同样地，我们将从外部正方形的角落开始。我们使用熟悉的前三个交换：左上 -> 右上，左上 -> 左下和左上 -> 右下。

7 2 1
4 5 6
9 8 3

请注意，矩阵几乎被旋转了；只有外部边缘中心的那四个顽固的值没有变化。但是，请注意，每个这样的值都只比我们旋转的角落位置多一个。如果我们继续使用固定起始点进行交换的模式，就像处理角落一样，我们可以像这样旋转最后四个值：上中 -> 右中，上中 -> 下中和上中 -> 左中。在索引方面，“上中”就是“左上”加一。同样，“右中”就是“右上”加一。对于某些索引，从极大索引（n-1）开始递减是有意义的。我将较小的中间索引称为i，将较大的中间索引称为j。

7 4 1
8 5 2
9 6 3

旋转一个2x2矩阵需要三次交换，旋转一个3x3矩阵需要六次交换，一般来说，旋转一个nxn矩阵需要n!次交换。我的while循环旋转矩阵中每个同心正方形的角落（每个正方形都比前一个小），然后我的for循环处理边缘之间角落以外的值。它会一直这样进行，直到没有更多内部正方形需要旋转，或者仅剩下一个1x1矩阵。

- Dyndrilliac

0

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

首先，我将2D数组列表分解为逐层的1D数组列表，然后旋转1D矩阵，再次放入矩阵形式。在将2D数组列表分解为1D数组列表时，我保存了元素在数组中的位置，以便我们可以将旋转后的矩阵放置在该位置。

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();
    }
}

- Amrit Malla

0

这是C#中的解决方案。每个 N x N 矩阵都将具有 floor (N/2) 个正方形循环。

例如- 4×4 和 5×5 都有 2 个可旋转层。

以下角落组合识别位置:

(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

这是将矩阵旋转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;
        }
    }
}

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

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);
}

- VAT

0

这是我的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;
}

- George Kagan

-1

简单的解决方案是：

int[][] a = { {00,01,02  }, { 10,11,12} ,{20,21,22}};
System.out.println(" lenght " + a.length);

int l = a.length;

for (int i = 0; i <l; i++) {

    for (int j = l - 1; j >= 0; j--) {
        System.out.println(a[j][i]);
    }
}

- saritha kota

2

这并不会旋转矩阵，它只是打印出矩阵的旋转形式。 - TheHardRock

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jason · Accepted Answer

概述

考虑一个样本矩阵可能长这样：

ABCD
EFGH
IJKL
MNOP

为了方便解释，ABCD被认为是第0行，EFGH是第1行，以此类推。第0行的第一个像素是A。

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

ABCD
E  H
I  L
MNOP

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

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

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

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

接下来的步骤是将左侧位置的值移动到顶部位置。例如：将M取出并放在A所在的位置。

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

下一步将底部位置的值移动到左侧位置。例如：将P取出并放到M所在的位置。

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

接下来的步骤是将右侧位置的值移动到底部位置。例如：将D移动到P所在的位置。

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

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

接下来是循环。

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

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

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

ABCD
EFGH
IJKL
MNOP

变成：

MIEA
NFGB
OJKC
PLHD

注意看外壳已经顺时针旋转，但内核没有移动。

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

MIEA
NJFB
OKGC
PLHD