516，贪心算法解按要求补齐数组
When the lord closes a door, somewhere he opens a window.
当主关上了一扇门，就会在别处打开一扇窗。
问题描述
给定一个已排序的正整数数组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
贪心算法解决
这题让从数组中找出任意数字都可以组成n，题中说了，数组是排序的。
假设数组中前k个数字能组成的数字范围是[1,total]，当我们添加数组中第k+1个数字nums[k](数组的下标是从0开始的)的时候，范围就变成了[1,total]U[nums[k],nums[k]]U[1+nums[k]，total+nums[k]]，这是个并集，可以合并成[1,total]U[nums[k],total+nums[k]]，我们仔细观察一下
1，如果左边的total<nums[k]-1，那么他们中间肯定会有空缺，不能构成完整的[1，total+nums[k]]。
举个例子
[1,5]U[7,10]，因为5<7-1，所以是没法构成[1,10]的
这个时候我们需要添加一个数字total+1。先构成一个更大的范围[1，total*2+1]。
这里为什么是添加total+1而不是添加total，我举个例子，比如可以构成的数字范围是[1,5]，如果需要添加一个构成更大范围的，我们应该选择6而不是选择5。
2，如果左边的total>=nums[k]-1，那么就可以构成完整的[1，total+nums[k]]，就不需要在添加数字了。
来看下代码
1public int minPatches(int[] nums, int n) {
2 //累加的总和
3 long total = 0;
4 //需要补充的数字个数
5 int count = 0;
6 //访问的数组下标索引
7 int index = 0;
8 while (total < n) {
9 if (index < nums.length && nums[index] <= total + 1) {
10 //如果数组能组成的数字范围是[1,total]，那么加上nums[index]
11 //就变成了[1,total]U[nums[index],total+nums[index]]
12 //结果就是[1,total+nums[index]]
13 total += nums[index++];
14 } else {
15 //添加一个新数字，并且count加1
16 total = total + (total + 1);
17 count++;
18 }
19 }
20 return count;
21}
另一种写法
上面组成数字的范围是闭区间，我们还可以改成开区间[1,total)，原理都一样，稍作修改即可，代码如下
1public int minPatches(int[] nums, int n) {
2 //累加的总和
3 long total = 1;
4 //需要补充的数字个数
5 int count = 0;
6 //访问的数组下标索引
7 int index = 0;
8 while (total <= n) {
9 if (index < nums.length && nums[index] <= total) {
10 //如果数组能组成的数字范围是[1,total)，那么加上nums[index]
11 //就变成了[1,total)U[nums[index],total+nums[index])
12 //结果就是[1,total+nums[index])
13 total += nums[index++];
14 } else {
15 //添加一个新数字，并且count加1
16 total <<= 1;
17 count++;
18 }
19 }
20 return count;
21}
●
●
●
●
如果觉得有用就点个"赞"吧