1089. Duplicate Zeros

1089. Duplicate Zeros

題目的要求很簡單,給定一個陣列,當陣列中出現零的時候,我們要多插入一個零,並且把接下來的數字依序往後移一個位置,但是於此同時我們要保持原先陣列的長度,如果數字在位移後的位置超過了原先陣列的長度,我們就不再保留這個數字。

這個題目是屬於記憶體操作的問題,這類型的問題通常都比較棘手,因為這些題目都有非常直覺性的實作方式,很容易在思考的時候被原先的思路給拉著走,導致在思考題目時容易有混淆的情況,不過還是會建議先想出直覺的寫法,面試時寫得出思路的重要性遠遠的比寫出最佳解的重要性來得高。

比較直覺的方法是我需要額外使用一個記憶體空間來儲存結果,接著遍歷這個陣列,當數字不為零的時候,把這個數字放入暫存的記憶體空間,如果遇到為零的時候在暫存的記憶體空間放入兩個零,並且移動兩步,當遍歷完陣列後再把結果取代掉原先的記憶體的內容,實作如下:

class Solution:
    def duplicateZeros(self, arr: List[int]) -> None:
        """
        Do not return anything, modify arr in-place instead.
        """
        n = len(arr)
        temp = []
        i = 0
        while i < n:
            if arr[i] == 0:
                temp += [0, 0]
                i += 1
            else:
                temp.append(arr[i])
                i += 1
        
        i = 0
        while i < n:
            arr[i] = temp[i]
            i += 1

但是上面的解法當然不是最佳解,因為這個解答雖然滿足了時間複雜度的最佳解,但是卻不是空間複雜度的最佳解。

當問題提供出上面的解法時,再思考是否有空間最佳解比較合適。

在 Python 中,有一個很方便的方法,那就是可以直接透過記憶體取代,但是這主要是利用到 Python 的語言特性,並不全然是這個題目的最佳解。

class Solution:
    def duplicateZeros(self, arr: List[int]) -> None:
        """
        Do not return anything, modify arr in-place instead.
        """
        i = 0
        n = len(arr)
        while i < n:
            if arr[i] == 0:
                arr[::] = arr[:i] + [0] + arr[i:n-1]
                i += 2
            else:
                i += 1

這個題目的最佳解其實滿難的,如果沒有任何提示在面試中可能可以想到輪廓,但是要在三十分鐘內想清楚再加上實作完是有點勉強,這種題目其實比較屬於需要觀察題目的特殊條件,透過特殊條件來完成程式的撰寫。

透過觀察,知道這個題目總共有幾個零其實是最重要的事情,如果一個零都沒有,那什麼都不用移動,接下來就是如果我們知道有 n 個零,那就是從後面開始數的數字,有 n 個數字我們不用保存。像是底下這個範例,我們知道只有一個零,那就是最後一個數字不用保存。

input = [1, 0, 2]
output = [1, 0, 0]

可是題目可能還有一種情況如下:

input = [1, 0, 0, 2]
output [1, 0, 0, 0]

上述的情況零有兩個,但是看起來卻像是最後只有一個數字 2 不要了,這種情況下我們要判斷的就是,當陣列開始位移的時候,如果零被位移到最後了,這時候我們還是要保持陣列的長度不變,所以最後一個數字為零,但是後面即使要再增加一個零,也是不需要的。

最後一個要考慮的點就是,如果題目真的有非常多個零,我們也不用全部都需要,因為如果有太多的零的時候,複製後超過長度的也都會被捨棄。

如果可以計算出上面最後有哪幾個數字不需要,那就可進而確認有哪些數字是需要的,知道這個條件後,只要把中間有零的地方複製出來就好了,不過這其實就是這個題目的難點,因為如果不想要使用額外的記憶體,那就需要用指針的方式直接把零插入到該位置上,但是這樣的話原先記憶體位址的數值就會不見了。

以上的思考是一般思考陣列的問題的想法,就是從起點往終點遍歷,這個題目的難點就在於能不能想到以下這點,那就是如果知道哪些數字需要保留了,直接從需要保留的最後一個數字開始查看,並且把這個數字直接覆蓋掉原先陣列的最後一個位置。

這樣會有什麼問題嗎?其實不會有問題的,因為在某個位置之後,後面的數字原本就不是我們需要保留的,因此直接覆蓋是沒有問題的,接著就再「往前」一個數字看,這時候如果是零,直接把倒數第二個跟第三個位置的數字全部都取代成零,這樣也不會有問題,因為往前數的指針,一定會比後面這個指針來得慢,頂多是一樣的。

如此以來就可以把上面兩個處理的模式分段處理這個題目:

zeros = 0
n = len(arr) - 1
i = 0

while i <= n - zeros:
    if arr[i] == 0:
        if i == n - zeros:
            arr[n] = 0
            n -= 1
            break
        zeros += 1
    i += 1

首先是要先計算出我們需要幾個零

class Solution:
    def duplicateZeros(self, arr: List[int]) -> None:
        """
        Do not return anything, modify arr in-place instead.
        """

        zeros = 0
        n = len(arr)
        i = 0

        while i < n - zeros:
            if arr[i] == 0:
                if i == n - zeros - 1:
                    arr[n - 1] = 0
                    n -= 1
                    break
                zeros += 1
            i += 1

        last = n - zeros - 1

        while last >= 0:
            if arr[last] == 0:
                arr[last + zeros] = 0
                zeros -= 1
                arr[last + zeros] = 0
            else:
                arr[last + zeros] = arr[last]
            last -= 1