Given an array, rotate the array to the right by k steps, where k is non-negative.
Example 1:
Input:[1,2,3,4,5,6,7]and 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: [-1,-100,3,99] and 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]
Note:
- Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
- Could you do it in-place with O(1) extra space?
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
n = len(nums)
k %= n
if n < 2 or k == 0:
return
nums[:] = nums[::-1]
nums[:k] = nums[:k][::-1]
nums[k:] = nums[k:][::-1]class Solution {
public void rotate(int[] nums, int k) {
if (nums == null) {
return;
}
int n = nums.length;
k %= n;
if (n < 2 || k == 0) {
return;
}
rotate(nums, 0, n - 1);
rotate(nums, 0, k - 1);
rotate(nums, k, n - 1);
}
private void rotate(int[] nums, int i, int j) {
while (i < j) {
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
++i;
--j;
}
}
}