題目敘述
題目會給定我們一個陣列和參數k，要求我們將陣列右旋k次，然後輸出內容。
例如[1,2,3,4,5] 右旋 2次，輸出就是[4,5,1,2,3]測試範例
Example 1:
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:
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]
約束條件
Constraints:
1 <= nums.length <= 105-231<= nums[i] <= 231- 10 <= k <= 105
Follow up:
- Try to come up with as many solutions as you can. There are at least three different ways to solve this problem.
- Could you do it in-place with
O(1)extra space?
演算法
除了第一直覺的創造新array再搬移的方法之外；其實，還有另一個透過三次翻轉來in-place實現(不需要額外創造新array)的方法。
原本的輸入，在右旋k次之後，會有下方的結果
- 原本頭部元素，包含頭部和之後的n-k個元素，移動到後端。
- 原本尾部元素，包含尾部和之前的k個元素，移動到前端。
因此，我們可以透過三次反轉(Reverse)來得到等價於右旋k次的效果。
- 第一次反轉，反轉整個array，目的是使頭尾顛倒。但是這一步有一個副作用，雖然頭尾顛倒了，但是次序也反轉了，因此我們需要第二次反轉和第三次反轉去修正這個副作用。
- 反轉前k項，這樣剛好原本尾巴的k個元素會剛好落在前端的位置。
- 反轉後n-k項，這樣剛好原本頭部的n-k的k個元素會剛好落在後端的位置。
程式碼
class Solution:
def reverse(self, nums: List[int], start, end):
# reverse array elements within [start, end] interval
while start < end:
nums[start], nums[end] = nums[end], nums[start]
start += 1
end -= 1
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
size = len(nums)
if k > size:
# eliminate redundant rotation which is over size
k = k % size
# reverse all elements
self.reverse( nums, 0, size-1)
# reverse first k elements
self.reverse( nums, 0, k-1)
# reverse last (size - k) elements
self.reverse( nums, k, size-1)
return
複雜度分析
時間複雜度:
O( n ) 每次反轉，最多耗費的成本是O(n) ，總共三次反轉=O(3n) = O(n)。
空間複雜度:
O( 1 ) 都是固定尺寸的臨時變數，function call stack也固定只有一層。
關鍵知識點
矩陣右移這個操作有點像在程式語言中的 >> bitwise右移運算，或者組合語言中的Right shift，觀念上相通的。
實作部分，透過畫圖，可以聯想到用reverse反轉來時做in-place實現，不需要去額外創造新的array去複製搬移。
Reference:
[1] Python/JS/Go/C++ O(n) by reverse [ With comment ] - Rotate Array - LeetCode
