從LeetCode學演算法

0189. Rotate Array (Easy)

Question

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:

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

分析/解題

題目給定一個陣列，將其往右輪轉k步，
要求直接將該陣列調整成輪轉後的結果。

這題一旦沒有Note的要求的話瞬間簡單一百倍 。
舉例來說，我們可以直接將後k項和前l-k項合併起來(l為陣列長度)，
就會是答案了；或者，將整個陣列重複銜接一次，取[(l-k):(2*l-k)]亦可。
(這兩個解法筆者列在Python的註解中供讀者參閱)
但，它們都不是in-place。

要考慮到in-place的話，我們必須知道，
一定有方法能讓他們跑到該有的地方，且不需用到超過O(1)以外的空間，
一般就意味著會在陣列進行swap的操作(交換兩個元素)。

先看一下原本的例子：
[1,2,3,4,5,6,7] and k = 3 -> [5,6,7,1,2,3,4]
先不論其他的部分，我們可以發現57從最尾端3個變成最前面的3個了；
與此同時，14自然從最前面4個變成最尾端4個。
我們先不論大家的順序，先將整個陣列倒過來的話，
可以先達到1~~4，5~~7分別占據目標的區塊的效果：[7,6,5 ,4,3,2,1]。
接著再比對一下，發現區塊是對了，但各自剛好被顛倒過一次 ，
那麼我們再對7~~5及4~~1分別各進行一次反轉 ，就會得到我們要的結果。

所以整個流程就會變成：

將整個陣列 進行反轉
將前k個數 進行反轉
將後l-k個數 進行反轉

反轉是很基本的操作，希望讀者能熟練掌握，
原則上利用two pointer的方式，每次將兩個元素進行交換 ，
並對pointer位置進行遞增/遞減的操作，直到相交 為止。
(例: [1 ,2,3,4 ]->[4,2 ,3 ,1]->[4,3,2,1])
Java的部分的兩數交換需要宣告一個暫存值tmp(temp)，
Python的部分則可直接使用a, b = b, a的方式進行交換。
最後，操作之前不要忘記將k先取除以l的餘數。

Java

Python

面試實際可能會遇到的問題

「時間/空間複雜度？」
(O(N), O(1)(如果是使用3次reverse的方法))

「如不限制空間複雜度必須O(1)？」
(可以參照上面Python程式碼中註解的做法)

相似及延伸

0031. Next Permutation (可以用到swap跟reverse的操作來解題)

Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~