189. 轮转数组

方法 1：多次反转

思路

先反转整体数组，再反转前 k 个([0, k - 1])，再反转后面剩余的([k, n - 1])，即为答案。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        def reverse(i: int, j: int) -> None:
            while i < j:
                nums[i], nums[j] = nums[j], nums[i]
                i += 1
                j -= 1
        n = len(nums)
        k %= n
        reverse(0, n - 1)
        reverse(0, k - 1)
        reverse(k, n - 1)

复杂度

时间复杂度：$O(n)$。
空间复杂度：$O(1)$。

题目链接

方法 2：数学 TODO

思路

代码

复杂度

时间复杂度：$O(n)$。
空间复杂度：$O(1)$。