1.题目
- 给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数
示例 1：
输入: nums = [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：
输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释:
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]
法一、利用python自带的reverse函数
-
思路：先翻转整个数组，再分别翻转前k个和后n-k个。
-
注意特殊情况：k有可能大于数组长度，用k %= n保证k小于n，如下图：
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
n=len(nums)
k %= n #保证k小于n
nums.reverse()
nums[0:k]= reversed(nums[0:k])
nums[k:n]= reversed(nums[k:n])
- 也可用切片实现翻转
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
n = len(nums)
k %= n
nums[:] = nums[::-1]#整个数组翻转
nums[:k] = nums[:k][::-1]#前k个翻转
nums[k:] = nums[k:][::-1] #从k到最后翻转
法二、辅助空间法
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
n = len(nums)
k %= n
tmp = nums[n - k:].copy()#先用一个临时数组存储后K个元素
for i in range(n - k - 1, -1, -1):#原数组元素向后移动k个
nums[i + k] = nums[i]
for i in range(0, k):#把临时数组存的元素放到数组前面
nums[i] = tmp[i]