按要求补齐数组
难度:
标签:
题目描述
给定一个已排序的正整数数组 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
提示：
1 <= nums.length <= 10001 <= nums[i] <= 104nums按 升序排列1 <= n <= 231 - 1
代码结果
运行时间: 27 ms, 内存: 16.2 MB
/*
* 思路:
* 使用 Stream 来简化代码实现。我们仍然需要遍历数组 nums，
* 从而确定当前 miss 是否需要补充新数字。
* 使用 Stream 不改变基本逻辑，但可以通过一些 Stream 操作使代码更简洁。
*/
import java.util.Arrays;
public class Solution {
public int minPatches(int[] nums, int n) {
long[] miss = {1};
int[] patches = {0};
Arrays.stream(nums).takeWhile(num -> miss[0] <= n).forEach(num -> {
while (num > miss[0] && miss[0] <= n) {
miss[0] += miss[0];
patches[0]++;
}
if (miss[0] <= n) {
miss[0] += num;
}
});
while (miss[0] <= n) {
miss[0] += miss[0];
patches[0]++;
}
return patches[0];
}
}解释
方法:
这个题解使用贪心算法的思路。维护一个变量s，表示当前数组能覆盖的连续区间的右端点。初始时s=1，表示可以覆盖[1,1]。遍历数组，对于每个数字，如果它不大于s，就把它加到s上，表示区间的右端点可以向右扩展到s+nums[i]。如果当前数字大于s，说明s到nums[i]之间有些数字不能被覆盖，需要添加一个数使得覆盖的区间扩大一倍，即s=s*2，同时把添加的数的个数ans加1。最终返回需要添加的数字个数ans。
时间复杂度:
O(log(n) + len(nums))
空间复杂度:
O(1)
代码细节讲解
🦆
为什么在题解中选择使用贪心算法来解决这个问题？
▷🦆
在题解中，当`nums[i]`大于`s`时，为什么选择将`s`乘以2，而不是添加一个正好填补到`nums[i]`的数字？
▷🦆
题解中提到增加`s`至少两倍的策略，这种操作是否总是最优，还是有可能存在通过添加更小数值得到更少添加次数的情况？
▷🦆
题解算法在遇到`nums`为空或者`nums`的第一个元素大于1时是如何处理的？
▷