You are given an n x n 2D matrix representing an image.
Rotate the image by 90 degrees (clockwise).
Note:
You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.
Example 1:
Given input matrix = [ [1,2,3], [4,5,6], [7,8,9] ], rotate the input matrix in-place such that it becomes: [ [7,4,1], [8,5,2], [9,6,3] ]Example 2:
Given input matrix = [ [ 5, 1, 9,11], [ 2, 4, 8,10], [13, 3, 6, 7], [15,14,12,16] ], rotate the input matrix in-place such that it becomes: [ [15,13, 2, 5], [14, 3, 4, 1], [12, 6, 8, 9], [16, 7,10,11] ]
题意：
In-place 顺时针旋转90度
Solution1: Try a simulation by matrix [2X2], find the principle how to rotate
i.e:
Original:1 23 4
Rotated:3 14 2
Q: How do we get value 3 from (1,0) to (0,0) ?
A: flip matrix from up to down
Flip up down from original:
3 41 2
Q: How do we put values 1 and 4 to their own places?
A: flip matrix by diagonal
Flip matrix by diagonal:
3 14 2
code
1 /* 2 Time:O(n^2). We use nested 2 for loop. 3 Space: O(1). We only used constant extra space. 4 */ 5 class Solution { 6 public void rotate(int[][] matrix) { 7 int n = matrix.length; 8 // flip matrix from up to down 9 for(int i = 0; i < n/2; i++){ 10 for(int j = 0; j< n; j++){ 11 swap(matrix, i, j, n-i-1, j); 12 } 13 } 14 //flip matrix by diagonal 15 for(int i = 0; i < n; i++){ 16 for(int j = i+1; j < n; j++){ 17 swap(matrix, i, j, j, i); 18 } 19 } 20 } 21 private void swap(int[][] matrix, int i, int j, int a, int b){ 22 int tmp = matrix[i][j]; 23 matrix[i][j] = matrix[a][b]; 24 matrix[a][b] = tmp; 25 } 26 }
转载于:https://www.cnblogs.com/liuliu5151/p/10708468.html
