forked from haoel/leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathRotateArray.java
More file actions
55 lines (51 loc) · 1.7 KB
/
RotateArray.java
File metadata and controls
55 lines (51 loc) · 1.7 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
// Source : https://leetcode.com/problems/rotate-array/description/
// Author : Tianming Cao
// Date : 2018-02-02
/**********************************************************************************
* Rotate an array of n elements to the right by k steps.
*
* For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].
*
* Note:
* Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
*
* Hint:
* Could you do it in-place with O(1) extra space?
* Related problem: Reverse Words in a String II
*
**********************************************************************************/
package rotateArray;
/**********************************************************************************
*
* For example, with n = 9 and k = 4, the array is [1,2,3,4,5,6,7,8,9]
* The train of thought is:
* 1. Reverse 1-5 to [5,4,3,2,1]
* 2. Reverse 6-9 to [9,8,7,6]
* 3. Reverse the entire array [5,4,3,2,1,9,8,7,6] to [6,7,8,9,1,2,3,4,5]
* It's a liner time and in-place algorithm
*
**********************************************************************************/
public class RotateArray {
public void rotate(int[] nums, int k) {
//bounds check
if (nums == null || nums.length == 0 || k == 0) {
return;
}
int n = nums.length;
//k may be larger than n
k = k % n;
rotateRange(0, n - k - 1, nums);
rotateRange(n - k, n - 1, nums);
rotateRange(0, n - 1, nums);
}
private void rotateRange(int start, int end, int[] array) {
for (int i = start, j = end; i < j; i++, j--) {
swap(array, i, j);
}
}
private void swap(int[] array, int i, int j) {
int t = array[i];
array[i] = array[j];
array[j] = t;
}
}