Given an array, rotate the array to the right by k steps, where k is non-negative.
Follow up:
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 <= 2 * 104-231 <= nums[i] <= 231 - 10 <= k <= 105Source
def rotate(nums, k):
n = len(nums)
if not k or k == n:
return
if k >= n:
k = k % n
nums[:] = nums[-k:] + nums[:-k]
def rotate(nums, k):
n = len(nums)
if not k or k == n:
return
if k >= n:
k = k % n
nums[:-k] = reversed(nums[:-k]) # nums[:-k].reverse() doesnt work
nums[-k:] = reversed(nums[-k:])
nums.reverse() # but here yes
nums = [1,2,3,4,5,6,7]
k = 3
rotate(nums, k)
print(nums)
[5, 6, 7, 1, 2, 3, 4]
nums = [-1,-100,3,99]
k = 2
rotate(nums, k)
print(nums)
[3, 99, -1, -100]
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?
def rotate(nums, k):
"""Using inplace reverse"""
def reverse(A, left, right):
while left < right:
A[left], A[right] = A[right], A[left]
left += 1
right -= 1
n = len(nums)
if not k or k == n:
return
if k >= n:
k = k % n
reverse(nums, 0 , n-1 )
reverse(nums, 0 , k-1 )
reverse(nums, k , n-1 )
def rotate(nums, k):
"""Using cyclic permutations"""
n = len(nums)
if not k or k == n:
return
if k >= n:
k = k % n
curr = start = 0
tmp = nums[curr]
for _ in range(n):
curr = (curr + k) % n
nums[curr], tmp = tmp, nums[curr]
if start == curr and start < n-1:
start += 1
curr = start
tmp = nums[curr]