LeetCode 修補數組：貪心策略最少添加元素覆蓋範圍

題目描述

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

貪心分析

維護當前可表示範圍 [1, miss)。若 nums[i] ≤ miss，則範圍擴展至 [1, miss + nums[i])；否則必須添加 miss，範圍翻倍至 [1, 2*miss)。

代碼實現 (Java)

public class Solution {
    public int minPatches(int[] nums, int n) {
        long miss = 1;
        int added = 0, i = 0;
        while (miss <= n) {
            if (i < nums.length && nums[i] <= miss) {
                miss += nums[i++];
            } else {
                miss <<= 1;
                ++added;
            }
        }
        return added;
    }
}

示例

• nums=[1,3], n=6 → 添加 1 次（添加 2）
• nums=[1,5,10], n=20 → 添加 2 次（添加 2,4）
• nums=[1,2,2], n=5 → 添加 0 次

複雜度

• 時間：O(m + log n)
• 空間：O(1)