↓Skip to main content
  1. Posts/

LeetCode-189 轮转数组

·1 min·
Table of Contents

LeetCode-189 轮转数组 #

Solution 1 #

最简单的做法当然是直接模拟. 但通常会要求思考出只有 $O(1)$ 空间复杂度原地算法. 一个技巧是: 数组轮转可以看成先翻转整个数组, 再分别翻转左右部分数组. 代码如下:

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        def reverse(nums: List[int], l: int, r: int):
            while l < r:
                nums[l], nums[r] = nums[r], nums[l]
                l += 1
                r -= 1
        n = len(nums)
        reverse(nums, 0, n - 1)
        reverse(nums, 0, k % n - 1)
        reverse(nums, k % n, n - 1)