-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy path189_Rotate_Array.java
More file actions
124 lines (110 loc) · 3.09 KB
/
Copy path189_Rotate_Array.java
File metadata and controls
124 lines (110 loc) · 3.09 KB
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
/*
* 189. Rotate Array
* Target: Given an array, rotate the array to the right by k steps, where k is non-negative.
* Eg => Input: [1,2,3,4,5,6,7] and k = 3. Output: [5,6,7,1,2,3,4]
* Difficulty：Easy
* Classification：Array
*/
/*
* Solution 1
* 2019-08-23 Runtime: 105 ms
* Algorithm: => Rotate one by one
* Time Complexity: O(n^k)?. Space Conplexity: O(1)
*/
class Solution {
public void rotate(int[] nums, int k) {
while (k > 0) {
int tmp = nums[nums.length - 1];
for (int i = nums.length - 2; i >= 0; i--) {
nums[i + 1] = nums[i];
}
nums[0] = tmp;
k--;
}
}
}
/*
* Solution 2
* 2019-08-23 Runtime: 1 ms
* Algorithm: => Separate original array, change the two parts position by using a new array.
* Time Complexity: O(n). Space Conplexity: O(n)
*/
class Solution {
public void rotate(int[] nums, int k) {
if (nums.length <= 1 || k == nums.length) {
return;
}
if (k > nums.length) {
k = k % nums.length;
}
int[] newNums = new int[nums.length];
for (int i = nums.length - k; i < nums.length; i++) {
newNums[i - nums.length + k] = nums[i];
}
for (int i = 0; i < nums.length - k; i++) {
newNums[i + k] = nums[i];
}
for (int i = 0; i < nums.length; i++) {
nums[i] = newNums[i];
}
}
}
/*
* Solution 3
* 2019-08-23 Runtime: 0 ms
* Algorithm: => Reverse. [1,2,3,4,5,6,7] and k = 3.
* 1. [1,2,3,4,5,6,7] => [4,3,2,1,5,6,7]
* 2. [4,3,2,1,5,6,7] => [4,3,2,1,7,6,5]
* 3. [4,3,2,1,7,6,5] => [5,6,7,1,2,3,4]
* Time Complexity: O(n). Space Conplexity: O(1)
*/
class Solution {
public void rotate(int[] nums, int k) {
if (nums.length <= 1 || k == nums.length) {
return;
}
k = k % nums.length;
reverse(nums, 0, nums.length - k - 1);
reverse(nums, nums.length - k, nums.length - 1);
reverse(nums, 0, nums.length - 1);
}
private void reverse(int[] nums, int l, int r) {
int tmp = 0;
while (l < r) {
tmp = nums[r];
nums[r] = nums[l];
nums[l] = tmp;
l++;
r--;
}
}
}
/*
* Solution 4
* 2019-08-24 Runtime: 0 ms
* Algorithm: => Loop.
* Time Complexity: O(n). Space Conplexity: O(1)
*/
class Solution {
public void rotate(int[] nums, int k) {
if (nums.length <= 1 || k == nums.length || k <= 0) {
return;
}
k %= nums.length;
int cur = nums[0], idx = k, head = 0;
for (int i = 0; i < nums.length; i++) {
if (idx == head) {
nums[idx] = cur;
head++;
idx++;
cur = nums[idx];
idx = (idx + k) % nums.length;
} else {
int tmp = nums[idx];
nums[idx] = cur;
cur = tmp;
idx = (idx + k) % nums.length;
}
}
}
}