《程序员面试金典》的第七题

    主要就是涉及矩阵的知识点：矩阵旋转90度。

第一种解法：辅助矩阵法

最简单的一种解法，主要思想就是用辅助矩阵记录元素旋转后的位置，但这样做的话，空间复杂度就为O(N^2)

注意一下对应位置，matrix[j][n-1-i]是旋转后的位置，因此需要在辅助矩阵的这个位置，输入对应的 matrix[i][j]。

class Solution {
    public void rotate(int[][] matrix) {
        int[][] m = new int[matrix.length][matrix[0].length]; //辅助矩阵
        // matrix[i][j] 旋转90度后的位置为 matrix[j][n-1-i]
        int n = matrix.length;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                m[j][n-1-i] = matrix[i][j]; //把辅助矩阵旋转对应的位置放入元素
            }
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                matrix[i][j] = m[i][j]; //复制辅助矩阵
            }
        }
    }
}

 

 第二种解法：线性代数性质

　　线性代数性质，先通过水平轴翻转，然后再通过主对角线反转，可以得到对应旋转90度的矩阵。

 

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        // 水平翻转
        for (int i = 0; i < n / 2; ++i) {
            for (int j = 0; j < n; ++j) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n - i - 1][j];
                matrix[n - i - 1][j] = temp;
            }
        }
        // 主对角线翻转
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
    }
}

 

 

方法三：一圈一圈地调整数据

这是最复杂的一种方法，它的主要思想是：每次修改矩阵的一圈数据，然后再修改下一圈，直到没有圈为止(一个或者零个元素)。 就和树的年轮一样。

主要代码思路：

temp = top[i]; //用一个临时变量储存
top[i] = left[i];
left[i] = bottom[i];
bottom[i] = right[i];
right[i] = temp;

 

 每次从左上角开始修改(因此需要一个临时变量记住左上角的元素)，然后是左下角，右下角，右上角，进行 圈的边长 - 1次 (两行共占一格，少一次遍历) 修改，就可以进行下一圈了。  

class Solution {
    public void rotate(int[][] matrix) {
        if(matrix.length==0||matrix.length!=matrix[0].length){
            //长度为0或不是N*N矩阵
            return; 
        }
        int n = matrix.length; //矩阵级数
        for(int i = 0;i<n/2;i++){ //总共要转 n/2 圈
            for(int j = i;j<n-1-i;j++){
                //用临时变量记录要被覆盖的值(左上方开始)
                int top = matrix[i][j];
                //左边(左下角开始)的值覆盖上边的值, 注意左边的数据,行在变化而列不变(一直是第一行)
                matrix[i][j] = matrix[n-1-j][i];
                //下边(右下角开始)的值覆盖左边的值，注意下边的数据,行一直是最后一行,而列在变化
                matrix[n-1-j][i] = matrix[n-1-i][n-1-j];
                //右边(右上角开始)的值覆盖下边的值, 右边的列一直是最后一列,行不断变化,始终为j
                matrix[n-1-i][n-1-j] = matrix[j][n-1-i];
                //上边(左上角开始)的值覆盖右边的值
                matrix[j][n-1-i] = top;
            }
        }
        return;
    }
}