class Solution {
public:
int minPatches(vector<int>& nums, int n) {
}
};
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
提示：
1 <= nums.length <= 10001 <= nums[i] <= 104nums 按 升序排列1 <= n <= 231 - 1原站题解
golang 解法, 执行用时: 4 ms, 内存消耗: 3.2 MB, 提交时间: 2023-06-06 09:52:20
func minPatches(nums []int, n int) (patches int) {
for i, x := 0, 1; x <= n; {
if i < len(nums) && nums[i] <= x {
x += nums[i]
i++
} else {
x *= 2
patches++
}
}
return
}
python3 解法, 执行用时: 48 ms, 内存消耗: 16.1 MB, 提交时间: 2023-06-06 09:51:58
class Solution:
def minPatches(self, nums: List[int], n: int) -> int:
patches, x = 0, 1
length, index = len(nums), 0
while x <= n:
if index < length and nums[index] <= x:
x += nums[index]
index += 1
else:
x <<= 1
patches += 1
return patches
javascript 解法, 执行用时: 56 ms, 内存消耗: 41.5 MB, 提交时间: 2023-06-06 09:51:44
/**
* @param {number[]} nums
* @param {number} n
* @return {number}
*/
var minPatches = function(nums, n) {
let patches = 0;
let x = 1;
const length = nums.length;
let index = 0;
while (x <= n) {
if (index < length && nums[index] <= x) {
x += nums[index];
index++;
} else {
x *= 2;
patches++;
}
}
return patches;
};
java 解法, 执行用时: 0 ms, 内存消耗: 41.8 MB, 提交时间: 2023-06-06 09:51:31
class Solution {
public int minPatches(int[] nums, int n) {
int patches = 0;
long x = 1;
int length = nums.length, index = 0;
while (x <= n) {
if (index < length && nums[index] <= x) {
x += nums[index];
index++;
} else {
x *= 2;
patches++;
}
}
return patches;
}
}
java 解法, 执行用时: 0 ms, 内存消耗: 41.6 MB, 提交时间: 2023-06-06 09:51:07
class Solution {
public int minPatches(int[] nums, int n) {
int count = 0, index = 0;
long curr = 1;
while (curr <= n) {
if (index >= nums.length || nums[index] > curr) {
count++;
curr *= 2;
} else {
curr += nums[index++];
}
}
return count;
}
}