【LeetCode】0189. Rotate Array

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

Example 1:

1
2
3
4
5
6
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:

1
2
3
4
5
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:

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


Related Topics:Dynamic ProgrammingBacktracking



解題邏輯與實作

這提示要求將 array 中的數字右旋 k 位,簡單來說,就是將所有的數字向後移動 k 位,而末尾 out of index 的部份則移到開頭。

這題說麻煩的部份是它最後希望我們提出三種不同實做的方法,另外要提供一種只需要 O(1) 空間的解法,這會花比較多時間。


解法1

最先想到的解法,就是使用 for 迴圈執行 k,每次迴圈執行時,記住最後一個數字後,將其他數字向後位移一位,再將所記住的數字放回開頭。

這種解法相當的直覺,算是暴力法了吧(笑,這種解法的空間複雜度會符合 O(1) 的要求,但時間複雜度應該會相當的高 O(kn)。為了減少執行次數,我將執行次數 kn 取餘數,因為當 k = n 時,相當於沒有做旋轉。

1
2
3
4
5
6
7
8
9
10
class Solution:
   def rotate(self, nums: List[int], k: int) -> None:
      n = len(nums)
      k %= n
      for i in range(k) :
         final = nums[n-1]
         for idx in range((n-1)-1,-1, -1):
            nums[idx+1] = nums[idx]

         nums[0] = final

另外,題目有要求 in-place instead,不然寫成這樣易讀性會更好

1
nums = [nums[n-1]] + nums[:-1]

最後果不其然 Time Limit Exceeded


解法2

另外想到基於解法1的解是直接將前 n-k 個向後移動 k 位,最後在將對後 k 移動到開頭。這樣時間複雜度會降成 O(n) ,但空間複雜度也會變成 O(n)

1
2
3
4
5
6
7
8
9
10
11
class Solution:
   def rotate(self, nums: List[int], k: int) -> None:
      n = len(nums)
      k %= n

      final = nums[n-k:]
      for idx in range((n-k)-1,-1, -1):
         nums[idx+k] = nums[idx]

      for idx in range(len(final)):
         nums[idx] = final[idx]

這次就被 accept 了,不過我一個月沒上來 LeetCode ,還多一個 Memory Usage 的比較耶~!
Runtime: 68 ms, faster than 46.18% of Python3 online submissions forRotate Array. Memory Usage: 13.4 MB, less than 5.04% of Python3 online submissions for Rotate Array.


解法3

第三個解法是從網路上找來的,有點類似翻轉 String 的方法,它先將前 n-k 個數字翻轉,再把後 k 個數字翻轉,最後將整個陣列都翻轉過來,就可以得到答案了。

這種解法的時間複雜度為 O(n) ,但空間複雜度可以降到 O(1)。個人覺得還蠻神奇的一個解法,滿佩服想到這種解法的人!

Example k = 3
1, 2, 3, 4, 5, 6, 7
4, 3, 2, 1, 5, 6, 7
4, 3, 2, 1, 7, 6, 5
5, 6, 7, 1, 2, 3, 4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
   def rotate(self, nums: List[int], k: int) -> None:
      n = len(nums)
      k %= n

      self.reverse(nums, 0, (n-k)-1)
      self.reverse(nums, n-k, n-1)
      self.reverse(nums, 0, n - 1)

   def reverse(self, nums, start, end):
      while start < end :
         nums[start], nums[end] = nums[end],  nums[start]
         start += 1
         end -= 1



其他連結

  1. 【LeetCode】0000. 解題目錄