【LeetCode】48. Rotate Image

问题描述

https://leetcode.com/problems/rotate-image/#/description

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?

将一个n x n矩阵顺时针翻转90度。最好事先就地翻转。

问题分析

方法1：使用翻转公式

n x n 矩阵顺时针90度翻转矩阵时，元素的位置变换公式为：

(i,j) -> (j, n-i)

根据变换公式，再创建一个二维矩阵即可实现要求。但没有实现就地翻转，因为需要另外创建矩阵。

方法二：上下翻转+中心对称翻转=顺时针旋转90度

先将矩阵上下翻转，然后将矩阵中心对称翻转，即可实现顺时针90度旋转。如下：

1 1 1    3 3 3    3 2 1
2 2 2 -> 2 2 2 -> 3 2 1
3 3 3    1 1 1    3 2 1

代码

public class Solution {
		/**
		 * 矩阵顺时针旋转90度，位置转换为：(i,j)->(j, n-i)
		 * @param matrix
		 */
	    public void rotate1(int[][] matrix) {
	        int n = matrix.length - 1;
	        if(n<=0) {
	        	return;
	        }
	        int[][] r_matrix = new int[n+1][n+1];
	        for(int i=0;i<matrix.length;i++) {
	        	for(int j=0;j<matrix.length;j++) {
	        		r_matrix[j][n-i] = matrix[i][j];
	        	}
	        }
	        for(int i=0;i<matrix.length;i++) {
	        	for(int j=0;j<matrix.length;j++) {
	        		matrix[i][j] = r_matrix[i][j];
	        	}
	        }
	    }
	    
	    /**
	     * 通过两次转换达到目的，首先是将行逆序排列，然后再执行中心对称翻转，如下：
	     * 1 1 1    3 3 3    3 2 1
	     * 2 2 2 -> 2 2 2 -> 3 2 1
	     * 3 3 3    1 1 1    3 2 1
	     * @param matrix
	     */
	    public void rotate(int[][] matrix) {
	    	// 上下翻转
	    	for(int i=0;i<matrix.length/2;i++) {
	    		int[] tmp = matrix[i];
	    		matrix[i] = matrix[matrix.length-1-i];
	    		matrix[matrix.length-1-i] = tmp;
	    	}
	    	// 中心对称翻转
	    	for(int i=0;i<matrix.length;i++) {
	    		for(int j=i+1;j<matrix.length;j++) {
	    			int tmp = matrix[i][j];
	    			matrix[i][j] = matrix[j][i];
	    			matrix[j][i] = tmp;
	    		}
	    	}
	    }
	    
	    
	}

LeetCode解题代码仓库：https://github.com/zgljl2012/leetcode-java