leetcode解题: Rotate Image (48)

发表于 | 分类于

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Follow up:
Could you do this in-place?

Show Company Tags
Show Tags

解法1：特殊解法　

如果是out-of-place的解法，就用
temp[j][n - 1 - j] = matrix[i][j]

如果要inplace的解法：可以有这么几种：

  • 先按逆对角线翻转一次，然后按ｘ轴中线翻转一次。
  • 或者呢也可以先transpose，然后把每一行翻转。
    个人感觉第二种解法比较好记也比较好写。不容易出错

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class Solution {
    public void rotate(int[][] matrix) {
        
        if (matrix.length == 0 || matrix[0].length == 0) {
            return;
        }
        
        int n = matrix.length;
        // flip along /
        for (int i = 0; i < n - 1; ++i) {
            for (int j = 0; j < n - 1 - i; ++j) {
               swap(matrix, i, j, n - 1 - j, n - 1 - i);
            }
        }
        
        // flip between 
        for (int i = 0; i < n / 2; ++i) {
            for (int j = 0; j < n; ++j) {
                swap(matrix, i, j, n - 1 - i, j);
            }
        }
        
        return;
    }
    
    private void swap(int[][] matrix, int ix, int iy, int jx, int jy) {
        int temp = matrix[ix][iy];
        matrix[ix][iy] = matrix[jx][jy];
        matrix[jx][jy] = temp;
        return;
    }
}