LeetCode 330.按要求补齐数组

题目描述

给定一个已排序的正整数数组 $nums$，和一个正整数 $n$ 。从 $[1, n]$ 区间内选取任意个数字补充到 $nums$ 中，使得 $[1, n]$ 区间内的任何数字都可以用 $nums$ 中某几个数字的和来表示。请输出满足上述要求的最少需要补充的数字个数。

示例 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] 区间里所有的数。
所以我们最少需要添加一个数字。

示例 2

输入: nums = [1,5,10], n = 20
输出: 2
解释:

我们需要添加 [2, 4]。

示例 3

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

题解

参考了 @小宇 发布在 LeetCode 中的 《简单思路（4行代码，超100%）》

对于已知 $[1, x]$ 都可覆盖，当再给一个数字 $y$ 时，可以得到新的覆盖区间为 $[1, x] \cup [1+y, x+y] \cup [y, y]$
可以将其分为如图两种情况讨论：
（蓝色为原本已覆盖区间，橙色为扩展后覆盖区间，虚线为无法覆盖的区间）

可覆盖区间动画

$y \rarr [1, x] = \begin{cases} [1, x+y] & y \le x \\ [1, x] \cup [y, x+y] & y \gt x \end{cases}$

只有新的数字 $y$ 大于原本的右边界时，才会导致可覆盖区间不连续。
需要特别注意的是，原本可覆盖的区间的组成数字可能远小于$x$，如只需要 $\{1,2,4\}$ 即可组成 $\{1,2,3,4,5,6,7\}$

$\begin{cases}1=1\\2=2\\3=1+2\\4=4\\5=1+4\\6=2+4\\7=1+2+4\end{cases}$

当插入新的数字 $5$ 时，可以获得新的区间 $[1, 12]$
$\begin{cases}6=1+5\\7=2+5\\8=1+2+5\\9=4+5\\10=1+4+5\\11=2+4+5\\12=1+2+4+5\end{cases}$

设 $m$ 为最小不可覆盖数，则当前已知的可覆盖区间为 $[1, m)$。从小到大判断数组中的元素 $nums[i]$ 是否小于等于 $m$。如果满足，则说明当前数可以扩展区间至 $[1, m + nums[i])$；否则，则说明将会获得区间 $[1, m)\cup [nums[i], m+nums[i])$，存在不可覆盖区间 $[m, nums[i])$。
要覆盖这个不可覆盖区间，需要添加一个（或多个）数字，使得区间扩展到 $nums[i]$。要尽可能少添加数字，那么应该尽可能使得扩展的范围更大，同时确保覆盖区间的连续。由上面的图片可知，添加的数字刚好与边界值相等时，扩展的距离最“远”。也即应该添加的数字为当前的边界 $m$，扩展后有 $m'=m+m$。重复该行为，直到 $m>nums[i]$
使用上面的策略，可以逐渐增大 $m$，最终使得 $m>n$，也即 $[1, n] \subseteq [1, m)$ 都可被覆盖

$m$ 扩大共有两种策略：增加数组中的数，扩大一倍。前者时间复杂度为 $O(l)$，后者时间复杂度为 $O(log(n))$。因此，总体的时间复杂度为 $O(l + log(n))$

该题目难点在于，将 寻找最少要插入的数个数 转换为 连续区间扩展，以及区间扩展的两种策略。

代码

Python 代码

class Solution:
    def minPatches(self, nums: List[int], n: int) -> int:
        l = len(nums)
        m = 1
        i = 0
        res = 0
        while m <= n:
            if i < l and nums[i] <= m:
                m += nums[i]
                i += 1
            else:
                m += m
                res += 1
        return res

C 代码

int minPatches(int* nums, int numsSize, int n){
    unsigned int m = 1, res = 0, i = 0;
    while (m <= n) m += (i < numsSize && nums[i] <= m) ? nums[i++] : (res++, m);
    return res;
}