Given an array, rotate the array to the right by k steps, where k is non-negative.
Example 1:
**Input:** nums = [1,2,3,4,5,6,7], k = 3
**Output:** [5,6,7,1,2,3,4]
**Explanation:**
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]
Example 2:
**Input:** nums = [-1,-100,3,99], k = 2
**Output:** [3,99,-1,-100]
**Explanation:**
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]
Constraints:
1 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1
0 <= k <= 105
Follow up:
Try to come up with as many solutions as you can. There are at least three different ways to solve this problem.
Could you do it in-place with O(1) extra space?
ac1: extra space
class Solution {
public void rotate(int[] nums, int k) {
// edge cases
if (nums == null || nums.length <= 1) return;
// init
int len = nums.length;
k = (k + len) % len;
int[] tmp = new int[k]; // tmp array store k element
int i = len - 1, j = tmp.length - 1;
// copy last k element to k array
for ( ; i >= len - k; i--, j--) {
tmp[j] = nums[i];
}
// move the rest in nums to the right
int i2 = len - 1;
for ( ; i >= 0; i--, i2--) {
nums[i2] = nums[i];
}
// copy tmp back;
i = 0;
for (int j2 = 0; j2 < tmp.length; j2++, i++) {
nums[i] = tmp[j2];
}
}
}
/*
O(n) time, O((k + len) % len) space
*/
ac2: in-place
class Solution {
public void rotate(int[] nums, int k) {
// edge cases
if (nums == null || nums.length <= 1) return;
k = (k + nums.length) % nums.length;
// reverse entire array
reverse(nums, 0, nums.length - 1);
// reverse first k element
reverse(nums, 0, k-1);
// reverse the rest
reverse(nums, k, nums.length - 1);
}
private void reverse(int[] nums, int s, int e) {
// boudary check
if (s >= e) return;
while (s < e) {
int tmp = nums[s];
nums[s] = nums[e];
nums[e] = tmp;
s++;
e--;
}
}
}
/*
O(n) time, O(1) space
*/