0330. Patching Array
====================
题目信息
--------
:题号: 0330
:难度: Hard
:主题: 升序正整数数组、子集和覆盖、添加元素、最少数量
:原题: `LeetCode 0330 `_
:重点: 每个数组元素至多使用一次、覆盖闭区间 ``[1,n]``、允许添加正整数、返回最少补丁数
题目重述
--------
给定按升序排列的正整数数组 ``nums`` 和正整数 ``n``。可以向数组中添加若干个正整数;添加完成后,要求对 ``[1, n]`` 中的每个整数,都能从最终数组中选取某些元素并用它们的和表示出来。
每个数组位置在一次求和中至多选用一次,数组中的重复值视为不同位置。返回满足完整覆盖要求所需添加元素的最少数量。``nums`` 的长度位于 ``[1, 1000]``,元素位于 ``[1, 10^4]``,``n`` 位于 ``[1, 2^31-1]``。
自建示例
--------
只存在一个覆盖缺口:
.. code-block:: text
输入:nums = [1, 2, 8],n = 15
输出:1
解释:原数组能表示 1 至 3;补入 4 后能表示 1 至 7,再结合 8 即可表示 1 至 15,所以只需一个补丁。
已有数组已经完整覆盖:
.. code-block:: text
输入: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++ 实现
--------
.. code-block:: cpp
class Solution {
public:
int minPatches(std::vector& nums, int n) {
long long reach = 1;
int index = 0;
int patches = 0;
while (reach <= n) {
if (index < static_cast(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)``。