🔗 🔴 330. Patching Array

tags: `貪心(Greedy)` `排序(Sorting)` `歸納法(Induction)`

題意

給定一個 已排序 的正整數陣列 $nums$ 和一個正整數 $n$ ，從 $[1, n]$ 區間內選取任意個數字補充到 $nums$ 中，使得 $[1, n]$ 區間內的任何數字都可以用 $nums$ 中某幾個數字的和來表示。

請返回最小需要補充的數字個數。

思路：歸納法(Induction) + 貪心(Greedy)

由小到大構造目標數，令 $s$ 表示當前可以構造的最大值，且將 $0$ 也視為可以構造的數，即 $[0, s]$ 區間內的所有整數都可以構造出來，則 $s+1$ 為下一個要構造的值。

若當前可以構造的數範圍是 $[0, s]$ ，在此基礎上若新增一個數 $c$ ，則可構造出 $[0+c, s+c]$ 。

若 $c \leq s$ ，則兩區間存在重疊，合併後可構造的範圍為 $[0, s+c]$ 。
若 $c = s+1$ ，則兩區間洽連續，也可合併成 $[0, s+c]$ 。
若 $c > s+1$ ，則兩區間不連續，無法構造出 $[0, s+c]$ 中的所有整數，此時需要補充 $s+1$ 這個數，補充後可以構造出 $[0, s+(s+1)]$ 中的所有整數。

複雜度分析

時間複雜度： $\mathcal{O}(m + \log \text{n})$ $O (m + lo g n)$ ，其中 $m$ $m$ 是 $nums$ $n u m s$ 的長度。
- 遍歷 $nums$ 的時間複雜度為 $\mathcal{O}(m)$ 。
- 每次補充數字後， $s$ 可以增加一倍，因此最多補充 $\log \text{n}$ 次。
空間複雜度： $\mathcal{O}(1)$

class Solution:
    def minPatches(self, nums: List[int], n: int) -> int:
        m = len(nums)
        ans, idx, s = 0, 0, 0
        
        while s < n:
            if idx < m and nums[idx] <= s + 1:
                s += nums[idx] # 可以構造出 [0, s + nums[idx]] 中的所有整數
                idx += 1
                continue
            else: # 因為後面的數字都 > s+1 ，所以無法構造出 s+1 了，需要補充 s+1
                s += s + 1
                ans += 1
        return ans

class Solution {
public:
    int minPatches(vector<int>& nums, int n) {
        int m = nums.size(), ans = 0, idx = 0;
        long long s = 0;
        while (s < n) {
            if (idx < m && nums[idx] <= s + 1) {
                s += nums[idx];
                idx++;
            } else {
                s += s + 1;
                ans++;
            }
        }
        return ans;
    }
};