經典陣列應用題 右旋陣列元素 Rotate Array_Leetcode #189

這題的題目在這裡:

題目敘述

題目會給定我們一個陣列和參數k，要求我們將陣列右旋k次，然後輸出內容。

測試範例

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 - 1
• 0 <= 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次之後，會有下方的結果

1. 原本頭部元素，包含頭部和之後的n-k個元素，移動到後端。
2. 原本尾部元素，包含尾部和之前的k個元素，移動到前端。

因此，我們可以透過三次反轉(Reverse)來得到等價於右旋k次的效果。

1. 第一次反轉，反轉整個array，目的是使頭尾顛倒。但是這一步有一個副作用，雖然頭尾顛倒了，但是次序也反轉了，因此我們需要第二次反轉和第三次反轉去修正這個副作用。
2. 反轉前k項，這樣剛好原本尾巴的k個元素會剛好落在前端的位置。
3. 反轉後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