LeetCode 筆記 - 189. Rotate Array

Posted on

題目在此 189. Rotate Array

給一個數列，你需要把數列最後面的數字移動到最前面 k 次

解題思維

如果 k == size 或者 size == 1，那就等於沒有做可以直接結束
所以 size 可以先跟 k 取一下 mod (因為 k = length => nothing happen)

接下來的動作就是直接移動 k 個數字到前面了

這題比較特別的地方是不需要回傳結果，而是在原本的記憶體內更改
所以有個特別的寫法是 nums[:]，這代表的是將等號右邊的結果逐一複製到 nums 這個記憶體位置，從而修改了原始陣列。

Space Complexity O(1)

在一些面試或競賽中，面試官可能會追問是否可以在 O(1) 的空間複雜度下完成這個任務。這意味著我們不能使用額外的陣列來存儲結果，而是需要在原地修改陣列。

這時候我們可以使用三次反轉 (Three Reversals) 的方法來達成這個目標：

  1. 反轉整個陣列。
  2. 反轉前 k 個元素。
  3. 反轉剩下的 n-k 個元素。

完成！

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """

        # step 1: k %= len(nums)
        # step 2: if k == 1: nums[-1:] + nums[:-1]
        #         if k == 2: nums[-2:] + nums[:-2]
        #         result = nums[-k:] + nums[:-k]
        # time complexity: O(n)
        # space complexity: O(n)

        k %= len(nums)

        nums[:] = nums[-k:] + nums[:-k]

也許你也會想看看