轮转数组

1、题目

图1

2、题解

辅助空间法

• \(k=k\%n\),将k限定在[0,n-1]范围内。
• 用\(i\)表示轮转前位置，\(i^`\)​表示轮转后位置:

\[ i'=(i+k)\%n=\begin{cases}i+k,\quad&i+k\leq n-1,\text{即}i\in[0,n-k-1]\\i+k-n,\quad&i+k\geq n,\text{即}i\in[n-k,n-1]\end{cases} \]

• 针对以上两端区间分别处理，用临时向量进行存储第二段区间。用\(i\)从\(n-k-1\)向0遍历，将\(i+k\)的位置更新为位置\(i\)的值。需要注意的是顺序从右向左。
• 最后再把临时向量赋值到[0,k-1]。

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        n = len(nums)
        k %= n
        # [n-k-1,n-1]
        tmp = nums[n - k:].copy()
        for i in range(n - k - 1, -1, -1):
            nums[i + k] = nums[i]
        for i in range(0, k):
            nums[i] = tmp[i]

双指针+翻转数组

先整体翻转数组，再分别翻转[0,k-1]和[k,n-1]的区间

def reverse(nums: List[int], left, right) -> None:
    i, j = left, right
    while i < j:
        nums[i], nums[j] = nums[j], nums[i]
        i+=1
        j-=1
class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        n = len(nums)
        k %= n
        reverse(nums, 0, n - 1)
        reverse(nums, 0, k - 1)
        reverse(nums, k, n - 1)

裴蜀定理（还没看懂