LeetCode 修補數組：最少添加元素覆蓋範圍 [1, n]

題目描述

給定已排序的正整數數組 nums 和整數 n，向數組中添加最少元素，使區間 [1, n] 內每個數都能由數組元素之和組成。返回最少添加次數。

貪心分析

維護當前能組成的範圍 [1, miss)，初始 miss = 1。遍歷數組：若當前元素 nums[i] <= miss，則範圍擴展為 [1, miss + nums[i])；否則必須添加 miss 這個數，範圍翻倍至 [1, 2*miss)，添加計數加一。重複直到 miss > n。

代碼實現 (C++)

class Solution {
public:
    int minPatches(vector<int>& nums, int n) {
        long miss = 1;
        int added = 0, i = 0;
        while (miss <= n) {
            if (i < nums.size() && nums[i] <= miss) {
                miss += nums[i++];
            } else {
                miss <<= 1; // miss *= 2
                ++added;
            }
        }
        return added;
    }
};

示例

• nums = [1, 3], n = 6：初始 miss=1，用 1 擴展到 2，無 2 需添加，miss=4，用 3 擴展到 7 > 6，添加 1 次。
• nums = [1, 5, 10], n = 20：添加 2 和 4，共 2 次。

複雜度

• 時間：O(m + log n)，m 為數組長度。
• 空間：O(1)。