Hard

题目描述

给定一个已排序的正整数数组 nums 和一个整数 n，向数组中添加/修补元素，使得 [1, n] 区间内的任何数字都可以由数组中某些元素的和来表示。

返回所需的最少修补数量。

示例 1：

输入：nums = [1,3], n = 6
输出：1
解释：
nums 的组合有 [1], [3], [1,3]，可以表示的和为：1, 3, 4。
现在如果我们将 2 添加到 nums 中， 组合变为: [1], [2], [3], [1,3], [2,3], [1,2,3]。
可以表示的和为 1, 2, 3, 4, 5, 6，涵盖了 [1, 6] 区间。
所以我们只需要 1 个补丁。

示例 2：

输入：nums = [1,5,10], n = 20
输出：2
解释：我们需要添加 [2, 4]。

示例 3：

输入：nums = [1,2,2], n = 5
输出：0

提示：

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 10^4
  • nums 按 升序排列
  • 1 <= n <= 2^31 - 1

解题思路

这道题的核心思想是贪心算法。我们需要理解一个关键性质：

如果数组能表示区间 [1, miss-1] 内的所有数字，那么当我们遇到一个数字 num：

  • 如果 num <= miss，则加入 num 后能表示 [1, miss + num - 1] 区间
  • 如果 num > miss，则存在缺口，我们需要添加数字 miss 来填补

算法步骤：

  1. 用变量 miss 表示当前无法表示的最小正整数
  2. 遍历数组，对每个数字判断是否能直接使用
  3. 如果当前数字 <= miss，可以扩展覆盖范围；否则需要添加 miss
  4. 重复直到覆盖整个 [1,n] 区间

时间复杂度分析： 每个原数组元素最多访问一次，添加的补丁数量是对数级别的，总体 O(m + log n)，其中 m 是数组长度。

空间复杂度： 只使用常数额外空间，O(1)。

这是一个经典的贪心问题，关键在于理解区间覆盖的性质和如何选择最优的补丁位置。

代码实现

class Solution {
public:
    int minPatches(vector<int>& nums, int n) {
        long miss = 1;  // 使用long避免溢出
        int patches = 0;
        int i = 0;
        
        while (miss <= n) {
            if (i < nums.size() && nums[i] <= miss) {
                // 当前数字可以使用，扩展覆盖范围
                miss += nums[i];
                i++;
            } else {
                // 需要添加补丁miss
                miss += miss;  // 等价于miss *= 2
                patches++;
            }
        }
        
        return patches;
    }
};

class Solution:
    def minPatches(self, nums: List[int], n: int) -> int:
        miss = 1  # 当前无法表示的最小正整数
        patches = 0
        i = 0
        
        while miss <= n:
            if i < len(nums) and nums[i] <= miss:
                # 当前数字可以使用，扩展覆盖范围
                miss += nums[i]
                i += 1
            else:
                # 需要添加补丁miss
                miss += miss  # 等价于miss *= 2
                patches += 1
        
        return patches

public class Solution {
    public int MinPatches(int[] nums, int n) {
        long miss = 1;  // 使用long避免溢出
        int patches = 0;
        int i = 0;
        
        while (miss <= n) {
            if (i < nums.Length && nums[i] <= miss) {
                // 当前数字可以使用，扩展覆盖范围
                miss += nums[i];
                i++;
            } else {
                // 需要添加补丁miss
                miss += miss;  // 等价于miss *= 2
                patches++;
            }
        }
        
        return patches;
    }
}

/**
 * @param {number[]} nums
 * @param {number} n
 * @return {number}
 */
var minPatches = function(nums, n) {
    let miss = 1;  // 当前无法表示的最小正整数
    let patches = 0;
    let i = 0;
    
    while (miss <= n) {
        if (i < nums.length && nums[i] <= miss) {
            // 当前数字可以使用，扩展覆盖范围
            miss += nums[i];
            i++;
        } else {
            // 需要添加补丁miss
            miss += miss;  // 等价于miss *= 2
            patches++;
        }
    }
    
    return patches;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(m + log n)m 为数组长度，每个元素最多访问一次，补丁数量最多 log n 个
空间复杂度O(1)只使用常数额外空间

相关题目