题目描述
给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。
示例 1:
输入: [1,2,3,4,5,6,7] 和 k = 3 输出: [5,6,7,1,2,3,4] 解释: 向右旋转 1 步: [7,1,2,3,4,5,6] 向右旋转 2 步: [6,7,1,2,3,4,5] 向右旋转 3 步: [5,6,7,1,2,3,4]
示例 2:
输入: [-1,-100,3,99] 和 k = 2 输出: [3,99,-1,-100] 解释: 向右旋转 1 步: [99,-1,-100,3] 向右旋转 2 步: [3,99,-1,-100]
说明:
解法
由题目可知,若移动位数为 k
,则表示将最后 k
位数字移动到数组前端,不妨以 l
表示数组长度,则数组中前 l-k
位数字向后移动 k
位。
不妨将最后 k
位数字中每一位下标为 i
的数字与下标为 i-k
的数字进行替换,不断减小 i
的值进行替换,若 l%k==0
则表示刚好能够全部替换完成;否则表示长度为 k
的数组,需要移动 k-(l%k)
位数字,递归该过程,直到刚好全部替换完成。
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
k=k%len(nums)
if not k:
return
def rot(end,gap):
i=end
while i>=gap:
nums[i],nums[i-gap]=nums[i-gap],nums[i]
i-=1
left=(end+1)%gap
if left:
rot(i,gap-left)
rot(len(nums)-1,k)