iOSLeetCode☞按要求补齐数组

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

示例 1:

输入: nums &＃61; [1,3], n &＃61; 6
输出: 1
解释:
根据 nums 里现有的组合 [1], [3], [1,3]&＃xff0c;可以得出 1, 3, 4。
现在如果我们将 2 添加到 nums 中&＃xff0c; 组合变为: [1], [2], [3], [1,3], [2,3], [1,2,3]。
其和可以表示数字 1, 2, 3, 4, 5, 6&＃xff0c;能够覆盖 [1, 6] 区间里所有的数。
所以我们最少需要添加一个数字。


示例 2:

输入: nums &＃61; [1,5,10], n &＃61; 20
输出: 2
解释: 我们需要添加 [2, 4]。


示例 3:

输入: nums &＃61; [1,2,2], n &＃61; 5
输出: 0


解题思路

对于正整数 x&＃xff0c;如果区间 [1, x - 1] 内的所有数字都已经被覆盖&＃xff0c;且 x 在数组中&＃xff0c;则区间 [1, 2x - 1] 内的所有数字也都被覆盖。证明如下。

• 对于任意 1 ≤ y

假设数字 x 缺失&＃xff0c;则至少需要在数组中补充一个小于或等于 x 的数&＃xff0c;才能覆盖到 x&＃xff0c;否则无法覆盖到 x。

如果区间 [1, x - 1] 内的所有数字都已经被覆盖&＃xff0c;则从贪心的角度考虑&＃xff0c;补充 x 之后即可覆盖到 x&＃xff0c;且满足补充的数字个数最少。在补充 x 之后&＃xff0c;区间 [1, 2x - 1] 内的所有数字都被覆盖&＃xff0c;下一个缺失的数字一定不会小于 2x。

由此可以提出一个贪心的方案。每次找到未被数组 nums 覆盖的最小的整数 x&＃xff0c;在数组中补充 x&＃xff0c;然后寻找下一个未被覆盖的最小的整数&＃xff0c;重复上述步骤直到区间 [1, n] 中的所有数字都被覆盖。

具体实现方面&＃xff0c;任何时候都应满足区间 [1, x - 1] 内的所有数字都被覆盖。令 x 的初始值为 1&＃xff0c;数组下标 index 的初始值为 0&＃xff0c;则初始状态下区间 [1, x - 1] 为空区间&＃xff0c;满足区间内的所有数字都被覆盖。进行如下操作。

• 如果 index 在数组 nums 的下标范围内且 nums[index] ≤ x&＃xff0c;则将 nums[index] 的值加给 x&＃xff0c;并将 index 的值加 1。

  • 被覆盖的区间从 [1, x - 1]扩展到 [1, x &＃43; nums[index] − 1]&＃xff0c;对 x 的值更新以后&＃xff0c;被覆盖的区间为 [1, x - 1]。

• 否则&＃xff0c;x 没有被覆盖&＃xff0c;因此需要在数组中补充 x&＃xff0c;然后将 x 的值乘以 2。

  • 在数组中补充 x 之后&＃xff0c;被覆盖的区间从 [1, x - 1] 扩展到 [1, 2x - 1]&＃xff0c;对 x 的值更新以后&＃xff0c;被覆盖的区间为 [1, x - 1]。

• 重复上述操作&＃xff0c;直到 x 的值大于 n。

由于任何时候都满足区间 [1, x - 1] 内的所有数字都被覆盖&＃xff0c;因此上述操作可以保证区间 [1, n] 内的所有数字都被覆盖。

又由于上述操作只在 x 不被覆盖时才在数组中补充 x&＃xff0c;如果不补充 x 则 x 无法被覆盖&＃xff0c;因此可以保证补充的数字个数最少。如果减少补充的数字个数&＃xff0c;则无法覆盖区间 [1, n] 内的所有数字。

代码

// 330. 按要求补齐数组func minPatches(_ nums: [Int], _ n: Int) -> Int {var patches &＃61; 0var x &＃61; 1, index &＃61; 0let length &＃61; nums.countwhile x <&＃61; n {if index < length && nums[index] <&＃61; x {x &＃43;&＃61; nums[index]index &＃43;&＃61; 1} else {x *&＃61; 2patches &＃43;&＃61; 1}}return patches}