LeetCode 旋转矩阵 java实现

旋转矩阵

题目描述：

给你一幅由 N × N 矩阵表示的图像，其中每个像素的大小为 4 字节。

请你设计一种算法，将图像旋转 90 度。

不占用额外内存空间能否做到？

示例

给定数组：

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

原地旋转90度：

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

解题思路

1. 当能使用额外内存空间时，算法较为简单，只需新建一个二维数组，通过旋转规律，使用两层for循环对新建数组添加旋转后的值即可完成。

2. 当不占用额外空间时，我们可先将二维数组按对角线进行旋转，如下所示：
   

3. 按对角线旋转后，对每一行元素按中心点进行两两交换即可，如下所示：
   

代码实现(不占用额外空间)：

class Solution {
    public void rotate(int[][] matrix) {
        int len = matrix.length;
        int temp = 0;
        for(int i=0;i<len-1;i++){
            for(int j=i+1;j<len;j++){
                temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        } 
        int mid = len/2;
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < mid; j++) {
                temp = matrix[i][j];
                matrix[i][j] = matrix[i][len - 1 - j];
                matrix[i][len - 1 - j] = temp;
            }
        }
    }
}