iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 28
1
Software Development

從LeetCode學演算法系列 第 28

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

所以整個流程就會變成:

  1. 整個陣列進行反轉
  2. 前k個數進行反轉
  3. 後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:

class Solution {
    public void rotate(int[] nums, int k) {
        if (nums == null || nums.length < 2) return;
        int len = nums.length;
        k = k % len;
        
        reverse(nums, 0, nums.length - k - 1);
        reverse(nums, nums.length - k, nums.length - 1);
        reverse(nums, 0, nums.length - 1);
    }
    
    private void reverse(int[] nums, int i, int j) {
        int tmp = 0;
        while(i < j) {
            tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
            i++;
            j--;
        }
    }
}

Python:

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        def numReverse(start, end):
            while start < end:
                nums[start], nums[end] = nums[end], nums[start]
                start += 1
                end -= 1
        k, n = k % len(nums), len(nums)
        if k:
            numReverse(0, n - 1)
            numReverse(0, k - 1)
            numReverse(k, n - 1)
'''
# Not in-place solution
class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        l = len(nums)
        k %= l
        if k > 0:
            nums[0:l] = nums[-k:] + nums[:-k]
class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        l = len(nums)
        k %= l
        if k > 0:
            nums[:] = (nums + nums)[l-k:l-k+l]
'''

面試實際可能會遇到的問題:
「時間/空間複雜度?」
(O(N), O(1)(如果是使用3次reverse的方法))

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

下篇預告:
0198. House Robber (Easy)


上一篇
[Day 27] 從LeetCode學演算法 - 0096. Unique Binary Search Trees (Medium)
下一篇
[Day 29] 從LeetCode學演算法 - 0198. House Robber (Easy)
系列文
從LeetCode學演算法30

1 則留言

0
hyj1116
iT邦新手 4 級 ‧ 2019-09-29 17:09:23

你好,請問Python區塊註解的code不是in place的做法嗎?
但是這句“Do not return anything, modify nums in-place instead.”看起來像是in place的做法?

Desolve iT邦新手 5 級 ‧ 2019-09-29 18:37:32 檢舉

Hi~
區塊註解內"Do not..."是原先題目放的,
那我再刪掉避免誤會。

此外,乍看之下是in place沒錯,
但實質上這個式子nums[0:l] = nums[-k:] + nums[:-k]
的右邊會分兩塊取出來,擺放在別的位置,
再將其重新按我們的要求置入nums中,
所以中途其實是有額外使用空間的(即便最後又還回去)。

你可以想像一下,
如果Python沒有額外在取這兩區塊時用別的空間放置,
那應該在第一段nums[-k:]重新排位的時候,
就會蓋過後面nums[:-k]要的東西了對吧XD
故按照這個邏輯推論,
實質上這麼做不可能不用到其他額外空間。

結論:
兩段取出來的東西加在一起,
在Python中會產生一個新的記憶體空間用來存它,
而我們指定存回去會讓最後東西回歸到nums中,
並不代表中途它沒用到別的記憶體。

希望有回答清楚你的問題 : )

我要留言

立即登入留言