補闕拾遺 補上缺少的數字 Patch Array_Leetcode #330 Greedy策略

Ben Wicks on Unsplash

題目敘述 Patching Array

題目給定一個整數陣列，
請問還要補上多少個數字，才能用這些數字的和拼湊出所有1~n的整數。

測試範例

Example 1:

Input: nums = [1,3], n = 6
Output: 1
Explanation:
Combinations of nums are [1], [3], [1,3], which form possible sums of: 1, 3, 4.
Now if we add/patch 2 to nums, the combinations are: [1], [2], [3], [1,3], [2,3], [1,2,3].
Possible sums are 1, 2, 3, 4, 5, 6, which now covers the range [1, 6].
So we only need 1 patch.

[1,2,3]可以拼出1~6地所以整數
1 = 1
2 = 2
3 = 3
4 = 3+1
5 = 3+2
6 = 3+2+1

Example 2:

Input: nums = [1,5,10], n = 20
Output: 2
Explanation: The two patches can be [2, 4].

[1,2,4,5,10] 可以拼出1~20地所以整數
1 = 1
2 = 2
3 = 2+1
4 = 4
5 = 5
6 = 5+1
7 = 5+2
8 = 5+2+1
9 = 5+4
10 = 10
11 = 10+1
12 = 10+2
13 = 10+2+1
14 = 10+4
15 = 10+4+1
16 = 10+5+1
17 = 10+5+2
18 = 10+5+2+1
19 = 10+5+4
20 = 10+5+4+1

Example 3:

Input: nums = [1,2,2], n = 5
Output: 0

[1,2,2] 可以拼出1~5地所以整數
1 = 1
2 = 2
3 = 2+1
4 = 2+2

觀察 湊整數的區間延伸

假設本來已經能湊出[1, x)的區間。

遇到新的數字y，假如y <= x 那麼可以延伸區間到[1, x+y)

只要把已知的方法再額外加上y即可。

遇到新的數字y，假如y > x ，代表需要補上一個新的數字x

補上新數字之後，可以延伸區間到[1, x+x) = [1, 2x)

接著再依循同樣的檢查邏輯，看看y 現在是 <= 2x 還是 > 2x。

最終，假如區間的終點x，已經大於n，代表我們可以用現有的數字做加法，湊出[1, n]區間內的所有整數。

示意圖

演算法 盡可能的延伸區間

承接觀察點的思考。

每遇到一個整數y，先確認是落在[1, x)區間內還是區間外。

落在區間內，就用現在這個整數去延伸區間到[1, x+y)

落在區間外，則補上一個整數x，延伸區間到[1, x+x) = [1, 2x)

接著再用同樣的規則檢查整數y

反覆迭代，一直到區間[1,x)能夠覆蓋n值為止。

程式碼 盡可能的延伸區間

class Solution:
    def minPatches(self, nums: List[int], n: int) -> int:
        
        # counting of patch, upper bound of coverage
        patchCount, limit = 0, 1

        # Initialization: we can cover interval [1, limit)

        # Array index
        index = 0

        # Push limit to cross over n with minimal count of patches
        while limit <= n:

            if index < len(nums) and nums[index] <= limit:

                # Now we can cover interval [1, limit + nums[index])
                limit += nums[index]
                index += 1

            else:
                # Current number is out of interval [1, limit)
                # patch 'limit' into array, now we can cover interval [1, limit + limit) = [1, 2*limit]
                patchCount += 1
                limit *= 2
        
        return patchCount

複雜度分析

時間複雜度: O( len(nums) + log n)

掃描每個陣列雲素耗費O( len(nums) )

延伸區間，直到覆蓋n為止，區間成長速度為兩倍，所需時間為O( log n)

空間複雜度: O(1)

所用到的都是固定尺寸的臨時變數，所需空間為O(1)

關鍵知識點

盡可能用最少的補充次數去延伸區間。(相當於貪心Greedy策略)

Reference:

[1] Patch Array