力扣 | 189.轮转数组
题目截图
方法一：三次反转当每当k等于n倍速，完成一整个循环，相当于没有变化。
利用k=k%n，去除无效变化的部分。
将整个数组分为前后两部分，三次反转后得到最后的结果。
例如：nums=[1, 2, 3, 4, 5, 6, 7]
k = 3
则分为[1, 2, 3, 4]和[5, 6, 7]两段。
第一次反转第一段，得[4, 3, 2, 1, 5, 6, 7]。
第二次反转第二段，得[4, 3, 2, 1, 7, 6, 5]。
第三次全部反转，得[5, 6, 7, 1, 2, 3, 4]。
复杂度时间复杂度
空间复杂度
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
n = len(nums)
k %= n
def swap(l, r):
while(l
完整测试代码
from typing import List
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
n = len(nums)
k %= n
def swap(l, r):
while(l
借助python的切片完成反转
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
n = len(nums)
k %= n
nums[:] = nums[::-1]
nums[:k] = nums[:k][::-1]
nums[k:] = nums[k:][::-1]
方法二：直接用python切片
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
n = len(nums)
k %= n
nums[:] = nums[n-k:] + nums[:n-k]
方法三：直接创建新数组
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
n = len(nums)
ans=[0]*n
for i in range(0, n):
ans[(i+k)%n] = nums[i]
for i in range(0, n):
nums[i] = ans[i]
方法四：环状替代
位置 0 的元素会放至 (0+k)mod n 处，反复这样移动就会形成一个移动闭环。
当然，这样并不能完全遍历每个元素，所以这样环状移动完成，回到最开始的位置后，就往下移动一个元素，然后再开始这样的环状移动。
何时能遍历完全部元素呢？
元素个数n和移动步长k的最大公约数就是环状移动的个数。
移动总步数=环状移动个数*环内移动步数
所以设置内外两个循环。
外层循环次数为最大公约数，内层循环移动替代，当替换回到开始的位置就退出内层循环。
import math
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
n = len(nums)
k %= n
count = math.gcd(k, n)
for start in range(0, count):
current = start
prev = nums[start]
while True:
next = (current + k) % n
nums[next], prev = prev, nums[next]
current = next
if next == start:
break
扩展：自定义最大公约数
辗转相除法
def my_gcd(x, y):
while x%y:
x, y = y, x%y
return y
迭代
def my_gcd(x, y):
return x if y==0 else self.my_gcd(x, x%y)
