/
_0048_RotateImage.java
127 lines (121 loc) · 3.37 KB
/
_0048_RotateImage.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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
package com.diguage.algorithm.leetcode;
import java.util.Objects;
import static com.diguage.algorithm.util.PrintUtils.printMatrix;
/**
* = 48. Rotate Image
*
* https://leetcode.com/problems/rotate-image/[Rotate Image - LeetCode]
*
* 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:
* [source]
* ----
* 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:
* [source]
* ----
* 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]
* ]
* ----
*
* @author D瓜哥, https://www.diguage.com/
* @since 2019-10-24 00:57:55
*/
public class _0048_RotateImage {
/**
* Runtime: 0 ms, faster than 100.00% of Java online submissions for Rotate Image.
*
* Memory Usage: 36.3 MB, less than 100.00% of Java online submissions for Rotate Image.
*/
public void rotate(int[][] matrix) {
if (Objects.isNull(matrix) || matrix.length == 0) {
return;
}
int length = matrix.length;
// 先交换行,这样操作更方便,但是也会有更多的额外空间。
for (int i = 0; i < length / 2; i++) {
int[] temp = matrix[i];
matrix[i] = matrix[length - 1 - i];
matrix[length - 1 - i] = temp;
}
// printMatrix(matrix);
for (int i = 0; i < length; i++) {
for (int j = 0; j < i; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
}
/**
* Runtime: 0 ms, faster than 100.00% of Java online submissions for Rotate Image.
*
* Memory Usage: 36.2 MB, less than 100.00% of Java online submissions for Rotate Image.
*/
public void rotate1(int[][] matrix) {
if (Objects.isNull(matrix) || matrix.length == 0) {
return;
}
int length = matrix.length;
for (int i = 0; i < length; i++) {
for (int j = 0; j < i; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
printMatrix(matrix);
for (int i = 0; i < length; i++) {
for (int j = 0; j < length / 2; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[i][length - j - 1];
matrix[i][length - j - 1] = temp;
}
}
}
public static void main(String[] args) {
_0048_RotateImage solution = new _0048_RotateImage();
int[][] array1 = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
printMatrix(array1);
solution.rotate(array1);
printMatrix(array1);
int[][] array2 = {{5, 1, 9, 11}, {2, 4, 8, 10}, {13, 3, 6, 7}, {15, 14, 12, 16}};
printMatrix(array2);
solution.rotate(array2);
printMatrix(array2);
}
}