Leetcode 189. Rotate Array

Posted on | | 阅读数
Words count in article: 212 | Reading time ≈ 1

Question

Solution1

最笨的最直观的方法，弹出最后一个元素然后直接插入到最前面。但是这样时间开销会很大。

1
2
3
4
5
6
7
8
9
class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        k = k % len(nums)
        for i in range(k):
            temp = nums.pop()
            nums.insert(0, temp)

Solution2

先定义一个首尾互换的函数，然后通过三次互换来实现。

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 numsreverse(start, end):
            while start < end:
                nums[start], nums[end] = nums[end], nums[start]
                start += 1
                end -= 1
        k, n = k % len(nums), len(nums)
        if k:
            numsreverse(0, n-1)
            numsreverse(0, k-1)
            numsreverse(k, n-1)

Solution3

直接将list前半部分和后半部分对掉

1
2
3
4
5
6
7
8
class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        k = k % n
        nums[:] = nums[n-k:] + nums[:n-k]