0189. Rotate Array - chasel2361/leetcode GitHub Wiki

Given an array, rotate the array to the right by k steps, where k is non-negative.

Example 1:
Input: [1,2,3,4,5,6,7] and k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

Example 2:
Input: [-1,-100,3,99] and k = 2
Output: [3,99,-1,-100]
Explanation:
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]

Note:
Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
Could you do it in-place with O(1) extra space?

這個題目的重點在於 in-place 的限制，如果沒有這個限制的話最快的做法是把 nums 複製一次接在尾端，然後去頭去尾

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        l = len(nums)
        k %= l
        if k > 0:
            nums[:] = (nums + nums)[l-k:l-k+l]

或者是將尾部剪下，加到前端

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        l = len(nums)
        k %= l
        if k > 0:
            nums[0:l] = nums[-k:] + nums[:-k]

這兩個方法的時間複雜度以及空間複雜度都是 O(1)

---

那如果有 in-place 的限制，做法就會稍微複雜一點

我最早的想法是，既然要往右輪的話，那就按照 k 的次數把最尾端的數插入到前端即可

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        k %= len(nums)
        for _ in range(k):
            nums.insert(0, nums.pop())

這樣做的時間複雜度是 O(N)，空間複雜度是 O(1)。不過因為呼叫 list.insert() 跟 list.pop() 都需要一些時間，速度不夠快

所以研究一下了其他人的寫法，發現可以利用反轉的方式處理，先把整個陣列反轉，在把前半段及後半段反轉即可

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        def reverse(start, end):
            while start < end:
                tmp = nums[start]
                nums[start] = nums[end]
                nums[end] = tmp
                start += 1
                end -= 1
        if k:
            k = k % len(nums)
            reverse(0, len(nums) - 1)
            reverse(0, k - 1)
            reverse(k, len(nums) - 1)

這個方法在反轉的部分應用了 two pointer 的概念，時間複雜度是 O(N)，空間複雜度是 O(1)

另外，也可以先創造一個 l 陣列，使其為我們要的結果，再把 l 複製進 nums 裡

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        n = len(nums)
        l = [None] * n
        for i in range(n):
            l[(i + k) % n] = nums[i]
            
        for i in range(n):
            nums[i] = l[i]

這樣的時間複雜度是 O(N)，跟前一個方法類似，但空間複雜度較大，為 O(N)