189. 轮转数组

题目链接

LeetCode 189题 “轮转数组” (Rotate Array) 是一个非常经典的算法题。通常所谓的“数学解法”主要指代两种 空间复杂度的解法：

  1. 环状替换 (Cyclic Replacements)：这是最硬核的数学解法，涉及到数论中的“最大公约数” (GCD)。
  2. 数组翻转 (Array Reversal)：这是最巧妙的解法，利用了翻转的性质。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        k = k % len(nums)
        def rev(nums: List[int], start: int, end: int) -> None:
            while start < end:
                nums[start], nums[end] = nums[end], nums[start]
                start += 1
                end -= 1
        rev(nums, 0, len(nums) - 1)
        rev(nums, 0, k - 1)
        rev(nums, k, len(nums) - 1)