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:

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 Programming、Backtracking

解題邏輯與實作

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

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

解法1

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

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

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，不然寫成這樣易讀性會更好

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

最後果不其然 Time Limit Exceeded。

解法2

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

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

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. 解題目錄

本文作者： 辛西亞．Cynthia
本文連結： 辛西亞的技能樹 / hackmd 版本
版權聲明： 部落格中所有文章，均採用 姓名標示-非商業性-相同方式分享 4.0 國際 (CC BY-NC-SA 4.0) 許可協議。轉載請標明作者、連結與出處！