題目

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

  • Follow-up: Could you do it in-place with O(1) extra space?
  • 題目連結

Example 1

1
2
3
4
5
6
Input: nums = [1,2,3,4,5,6,7], 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

1
2
3
4
5
Input: nums = [-1,-100,3,99], 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]

解釋題目

給你一個 array，叫 nums，以及 k 值，k 是要向右移動的步數。舉例來說，當 k 是 3 時，每個 array 中的值會向右移動 3 個位置，以此類推。題目設定 k 值一定是正的，所以不用考慮負值的情況。

思路 (1)

這題最直覺的想法就是 deep copy 同一個陣列出來，然後遍歷整個 array，把每個值向右移動 k 個位置。

  1. 需要注意的是 k 如果走的步數是 nums 的長度，代表走回原位置，所以 k 要取的值是除以 len(nums) 的餘數。
  2. 如果向右走超過 nums 的長度，要減去 len(nums)，然後 從 nums 前面遞補。

程式碼 (1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import copy

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        length = len(nums)
        step = k % length
        new_nums = copy.deepcopy(nums)
        for i in range(length):
            if i + step >= length:
                nums[i + step - length] = new_nums[i]
            else:
                nums[i + step] = new_nums[i]

思路 (2)

然而，這樣寫法的「空間複雜度」是 O(n)。假設 nums 長度為 n，就必須要開 n 個空間。也就是說， nums 如果越長，需要的空間就會越多。O(1) 的概念是，不論 array 多長，我只需要固定數量的變數，就可以把整個 array 向右移動 k 步。這題的想法可以從結果往回推。

  1. 向右移 k 步，可以想像成，要從 array 的最後面，移動 k 個數字，到 array 的最前面。所以，以範例來說 [1, 2, 3, 4, 5, 6, 7]，向右移動 3 步，就是要把 5, 6, 7 移到前面，1, 2, 3, 4 會往後移。
  2. 藉由這樣移動，就會發現把 5, 6, 7 反轉，再把 1, 2, 3, 4 反轉，然後拼接起來，正好就是 [7, 6, 5, 4, 3, 2, 1]。
  3. 所以整題的做法就是: 先把整個 array 反轉，把前 k 個 reverse，再把後 k-1 個 reverse。
  4. 要先把 reverse 寫出來，雙指針大步分用 while 去解。
  5. 注意: 如果 k 向右走了 array 的總長，就是繞回原位，所以 k 要除以 len(nums) 取餘數。即 k % len(nums)，題目有規定 k 為正，所以不用考慮負數情況。
  6. nums 是 in-place 變動，不用回傳值

圖像拆解

步驟拆解 1

步驟拆解 2

步驟拆解 3

程式碼 (2)

  • reverse 可以說是標準的 雙指針 題目，以 [1, 2, 3, 4, 5, 6, 7] 為例，首先把兩個指針設定在頭尾，命名為 left 跟 right。
  • 雙指針通常是用 while 迴圈 去做，當指針 left < right 時，兩個位置的值就互換。
  • 每一次迴圈完成，左指針 ( left ) 要向右走，右指針 ( right ) 要向左走，兩指針相遇就停止。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """

        def rev(left, right):
            while left < right:
                # 此寫法，右邊是將 nums[right], nums[left] 設定為變數的意思
                nums[left], nums[right] = nums[right], nums[left]
                left += 1
                right -= 1

        length = len(nums)
        k = k % length

        rev(0, length - 1)
        rev(0, k - 1)
        rev(k, length - 1)