題目出處
難度
Medium
題目分類
array, math, two pointers
個人範例程式碼
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
len_nums = must_visited = len(nums)
start_idx = 0
while(must_visited != 0):
i = start_idx
prev = nums[start_idx]
while(True):
next_i = (i+k)%len_nums
save = nums[next_i] # save next
nums[next_i] = prev # use prev to change next
prev = save # next give to keep
i = next_i # move to next index
must_visited -= 1 # prevent for len_nums can divide k
if i == start_idx: # return to start
break
start_idx += 1 # prevent for len_nums can divide k
Time Complexity
O(n)
Space Complexity
O(1) # 這題有特別要求希望是這個空間
算法說明
題目要求空間 O(1)，通常就表示這個題目「高機率」可以用 swap 的方式解出來 (想辦法只用交換的)
題目提到「in-place」，表示這題目可以用 swap 的方法解的「可能性很高」，不過這個提示沒有上方機率那麼高，有時候我們也是可以另外 assign 空間再去進行「in-place」的動作。
方法一 – circular array
直覺上，我們可以將此 array 當作一個環，不斷的交換一個循環，直到回到起點結束交換。
為了方便起見，以下的例子我們故意將 index 與裡面的元素值取相同。
我們可以觀察，k=2 時，我們下一個移動的目標 next_i = (i+k)%(array長度) <- 取餘數
我們再次觀察，k=3 時，我們下一個移動的目標 next_i = (i+k)%(array長度) <- 取餘數
注意!! 此方法有個陷阱!!
當「矩陣的長度可以被 k 整除時，會有快速循環的現象」，
例如「len(nums) = 4, k = 2」
[0,1,2,3]
如果只照上述循環後，我們就只會變更 [2,1,0,3] <- 注意只有 0, 2 交換。
為了避免此問題，我們需要另外設計一個 visited 的機制，確保每一個位置都有換過!!
範例程式碼
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
len_nums = must_visited = len(nums)
start_idx = 0
while(must_visited != 0):
i = start_idx
prev = nums[start_idx]
while(True):
next_i = (i+k)%len_nums
save = nums[next_i] # save next
nums[next_i] = prev # use prev to change next
prev = save # next give to keep
i = next_i # move to next index
must_visited -= 1 # prevent for len_nums can divide k
if i == start_idx: # return to start
break
start_idx += 1 # prevent for len_nums can divide k
corner case 特殊情況處理
處理當 len(nums) = 0 或 k 的情況，基本上都不用做事情，可以節省時間。
上述範例沒有做，但程式碼已經可以處理這個情況。
Boundary conditions/ Edge conditions 邊際情況處理
- 結束位置在，當 index 返回出發點時。
- 但要讓整個交換完成，需要注意是否有整除問題，所以真正結束是在 visited 剛好等於 array 長度時，
期間我們需要去變換起始的 index 位置。
方法二 – recursive
這個方法我也是參考 discussion 看到的，非常酷的做法!
他運用的概念是「矩陣反轉兩次後，會回到原位置」。
因此如果在第二步驟，我們依照「目標 k 位置」進行「分別反轉」，
就可以得到答案。
舉例：k = 3，以下為了方便起見，直接讓 index 值等於元素值
[0,1,2,3,4,5,6] <- 原始位置
[6,5,4,3,2,1,0] <- 第一次 全反轉
[4,5,6,0,1,2,3] <- 拆兩次反轉 0~k-1, k~len(nums)-1
範例程式碼
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
if len(nums) <= 1:
return
else:
k = k % len(nums)
self.reverse(nums, 0, len(nums)-1)
self.reverse(nums, 0, k-1)
self.reverse(nums, k, len(nums)-1)
return
def reverse(self, nums, start, end):
while start < end:
nums[start], nums[end] = nums[end], nums[start]
start += 1
end -= 1