11package com .fishercoder .solutions ;
22
3- /**
4- * 189. Rotate Array
5-
6- Given an array, rotate the array to the right by k steps, where k is non-negative.
7-
8- Example 1:
9- Input: [1,2,3,4,5,6,7] and k = 3
10- Output: [5,6,7,1,2,3,4]
11- Explanation:
12- rotate 1 steps to the right: [7,1,2,3,4,5,6]
13- rotate 2 steps to the right: [6,7,1,2,3,4,5]
14- rotate 3 steps to the right: [5,6,7,1,2,3,4]
15-
16- Example 2:
17- Input: [-1,-100,3,99] and k = 2
18- Output: [3,99,-1,-100]
19- Explanation:
20- rotate 1 steps to the right: [99,-1,-100,3]
21- rotate 2 steps to the right: [3,99,-1,-100]
22-
23- Note:
24- Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
25- Could you do it in-place with O(1) extra space?
26- * */
27-
283public class _189 {
294
30- public static class Solution1 {
31- /**
32- * O(n*k) time
33- * O(1) space
34- */
35- public void rotate (int []nums ,int k ) {
36- int tmp ;
37- for (int i =0 ;i <k ;i ++) {
38- tmp =nums [nums .length -1 ];
39- for (int j =nums .length -1 ;j >0 ;j --) {
40- nums [j ] =nums [j -1 ];
5+ public static class Solution1 {
6+ /**
7+ * O(n*k) time
8+ * O(1) space
9+ */
10+ public void rotate (int []nums ,int k ) {
11+ int tmp ;
12+ for (int i =0 ;i <k ;i ++) {
13+ tmp =nums [nums .length -1 ];
14+ for (int j =nums .length -1 ;j >0 ;j --) {
15+ nums [j ] =nums [j -1 ];
16+ }
17+ nums [0 ] =tmp ;
18+ }
4119 }
42- nums [0 ] =tmp ;
43- }
4420 }
45- }
4621
47- public static class Solution2 {
48- /**
49- * using an extra array of the same size to copy it
50- * O(n) time
51- * O(n) space
52- */
53- public void rotate (int []nums ,int k ) {
54- int len =nums .length ;
55- int []tmp =new int [len ];
56- for (int i =0 ;i <len ;i ++) {
57- tmp [(i +k ) %len ] =nums [i ];
58- }
59- for (int i =0 ;i <len ;i ++) {
60- nums [i ] =tmp [i ];
61- }
22+ public static class Solution2 {
23+ /**
24+ * using an extra array of the same size to copy it
25+ * O(n) time
26+ * O(n) space
27+ */
28+ public void rotate (int []nums ,int k ) {
29+ int len =nums .length ;
30+ int []tmp =new int [len ];
31+ for (int i =0 ;i <len ;i ++) {
32+ tmp [(i +k ) %len ] =nums [i ];
33+ }
34+ for (int i =0 ;i <len ;i ++) {
35+ nums [i ] =tmp [i ];
36+ }
37+ }
6238 }
63- }
6439
65- public static class Solution3 {
66- /**
67- * reverse three times
68- * O(n) time
69- * O(1) space
70- */
71- public void rotate (int []nums ,int k ) {
72- int len =nums .length ;
73- k %=len ;
74- reverse (nums ,0 ,len -1 );
75- reverse (nums ,0 ,k -1 );
76- reverse (nums ,k ,len -1 );
77- }
40+ public static class Solution3 {
41+ /**
42+
43+
44+
45+
46+ public void rotate (int []nums ,int k ) {
47+ int len =nums .length ;
48+ k %=len ;
49+ reverse (nums ,0 ,len -1 );
50+ reverse (nums ,0 ,k -1 );
51+ reverse (nums ,k ,len -1 );
52+
7853
79- private void reverse (int []nums ,int start ,int end ) {
80- while (start <end ) {
81- int tmp =nums [start ];
82- nums [start ] =nums [end ];
83- nums [end ] =tmp ;
84- start ++;
85- end --;
86- }
54+ private void reverse (int []nums ,int start ,int end ) {
55+ while (start <end ) {
56+ int tmp =nums [start ];
57+ nums [start ] =nums [end ];
58+ nums [end ] =tmp ;
59+ start ++;
60+ end --;
61+ }
62+ }
8763 }
88- }
8964}