Description
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?
Solutions
1. 多次旋转
# Time: O(n)
# Space: O(1)
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
if not nums:
return
n = len(nums)
if k >= n:
k %= n
self.reverse_list(nums, 0, n-k-1)
self.reverse_list(nums, n-k, n-1)
self.reverse_list(nums, 0, n-1)
def reverse_list(self, nums, l, r):
if l < 0 or r >= len(nums):
return False
while l < r:
nums[l], nums[r] = nums[r], nums[l]
l += 1
r -= 1
return True
# 34/34 cases passed (72 ms)
# Your runtime beats 58.01 % of python3 submissions
# Your memory usage beats 5.09 % of python3 submissions (14 MB)
2. 更快的方法
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
length = len(nums)
k = k % length
if k == 0:
return
for i in range(self.gcd(length, k)):
prev = nums[i]
j = (i + k) % length
while j != i:
next_n = nums[j]
nums[j] = prev
prev = next_n
j = (j+k) % length
nums[j] = prev
def gcd(self, a, b):
if b == 0:
return a
else:
return self.gcd(b, a % b)
# 34/34 cases passed (60 ms)
# Your runtime beats 90.55 % of python3 submissions
# Your memory usage beats 5.09 % of python3 submissions (14.2 MB)