三次反转
对于[1,2,3,4,5,6,7][1,2,3,4,5,6,7],
根据k=k%nk=k%n,将数组分为两段:
第一段,对应数组下标范围[0,n-k-1][0,n−k−1]段,即[1,2,3,4][1,2,3,4]
第二段,对应数组下标范围[n-k,n-1][n−k,n−1],即[5,6,7][5,6,7]
分为三步:
- 反转第一段,[4,3,2,1,5,6,7]
- 反转第二段,[4,3,2,1,7,6,5]
- 反转整体,[5,6,7,1,2,3,4]
code:
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
n = len(nums)
k = k%n
def swap(l,r):
while l < r:
nums[l],nums[r] = nums[r],nums[l]
l += 1
r -= 1
swap(0,n-k-1)
swap(n-k,n-1)
swap(0,n-1)
# insert
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
n = len(nums)
k %= n
for _ in range(k):
nums.insert(0, nums.pop())
网友评论