LeetCode 330.按要求补齐数组

题目描述

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

示例 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][1, x] 都可覆盖，当再给一个数字 yy 时，可以得到新的覆盖区间为 [1,x]∪[1+y,x+y]∪[y,y][1, x] \cup [1+y, x+y] \cup [y, y]
可以将其分为如图两种情况讨论：
（蓝色为原本已覆盖区间，橙色为扩展后覆盖区间，虚线为无法覆盖的区间）

可覆盖区间动画

y→[1,x]={[1,x+y]y≤x[1,x]∪[y,x+y]y>xy \rarr [1, x] = \begin{cases} [1, x+y] & y \le x \\ [1, x] \cup [y, x+y] & y \gt x \end{cases}

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

{1=12=23=1+24=45=1+46=2+47=1+2+4\begin{cases}1=1\\2=2\\3=1+2\\4=4\\5=1+4\\6=2+4\\7=1+2+4\end{cases}

当插入新的数字 55 时，可以获得新的区间 [1,12][1, 12]
{6=1+57=2+58=1+2+59=4+510=1+4+511=2+4+512=1+2+4+5\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}

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

mm 扩大共有两种策略：增加数组中的数，扩大一倍。前者时间复杂度为 O(l)O(l)，后者时间复杂度为 O(log(n))O(log(n))。因此，总体的时间复杂度为 O(l+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;
}