0330. Patching Array

题目信息

题号:

0330

难度:

Hard

主题:

升序正整数数组、子集和覆盖、添加元素、最少数量

原题:

LeetCode 0330

重点:

每个数组元素至多使用一次、覆盖闭区间 [1,n]、允许添加正整数、返回最少补丁数

题目重述

给定按升序排列的正整数数组 nums 和正整数 n。可以向数组中添加若干个正整数;添加完成后,要求对 [1, n] 中的每个整数,都能从最终数组中选取某些元素并用它们的和表示出来。

每个数组位置在一次求和中至多选用一次,数组中的重复值视为不同位置。返回满足完整覆盖要求所需添加元素的最少数量。nums 的长度位于 [1, 1000],元素位于 [1, 10^4],n 位于 [1, 2^31-1]。

自建示例

只存在一个覆盖缺口:

输入:nums = [1, 2, 8],n = 15
输出:1
解释:原数组能表示 1 至 3;补入 4 后能表示 1 至 7,再结合 8 即可表示 1 至 15,所以只需一个补丁。

已有数组已经完整覆盖:

输入:nums = [1, 2, 4],n = 7
输出:0
解释:通过选择这些元素的不同子集,可以表示 1 到 7 的每个整数,不需要添加新值。

维护当前连续覆盖的右端

设 reach 表示当前元素可以覆盖的连续区间为 [1, reach - 1],初始没有元素,所以 reach = 1。若下一个未处理的原数组元素 nums[i] <= reach,它可以和已有子集组合,把覆盖右端扩展到 reach + nums[i] - 1,因此令 reach += nums[i]。

如果 nums[i] > reach,金额 reach 无法由已有元素表示,而任何更大的补丁也不能表示这个缺口;最小且最有用的选择只能是补入 reach。加入它后,原来 [1, reach - 1] 的所有数与补丁组合,恰好连续覆盖到 2 * reach - 1,所以令 reach += reach。只要 reach <= n 就必须继续补齐或吸收原数组元素。

C++ 实现

class Solution {
public:
    int minPatches(std::vector<int>& nums, int n) {
        long long reach = 1;
        int index = 0;
        int patches = 0;

        while (reach <= n) {
            if (index < static_cast<int>(nums.size())
                && nums[index] <= reach) {
                reach += nums[index++];
            } else {
                reach += reach;
                ++patches;
            }
        }
        return patches;
    }
};

代码分析

数组已升序排列,所以一旦当前元素大于缺口,后面的原元素也不可能先填补它;补入 reach 是在该时刻能把连续覆盖区间扩展得最远的最优选择。使用 long long 是因为覆盖端点会超过 n 才停止,而 n 接近 32 位上界。每个原数组元素最多处理一次,时间复杂度为 O(nums.size()),额外空间为 O(1)。