Google
330 Patching Array

1. Question

Given a sorted positive integer arraynumsand an integern, add/patch elements to the array such that any number in range[1, n]inclusive can be formed by the sum of some elements in the array. Return the minimum number of patches required.
Example 1: nums=[1, 3],n=6 Return1.
Combinations ofnumsare[1], [3], [1,3], which form possible sums of:1, 3, 4. Now if we add/patch2tonums, the combinations are:[1], [2], [3], [1,3], [2,3], [1,2,3]. Possible sums are1, 2, 3, 4, 5, 6, which now covers the range[1, 6]. So we only need1patch.
Example 2: nums=[1, 5, 10],n=20 Return2. The two patches can be[2, 4].
Example 3: nums=[1, 2, 2],n=5 Return0.

2. Implementation

思路:
(1) 这题很有意思,要求我们找到数组里需要加多少个数,使得数组可以表示[1,n]。假设我们当前在nums[i]这个位置上可以表示范围为[1,n]的数,n为nums[0]到nums[i]所有数的和,当我们在数组加入n + 1时,我们就可以表示[1, 2n + 1]的数了,其中[n + 1, 2n + 1]这个范围的数可以通过新加的n + 1表示。
(2) 所以我们的做法是用一个变量miss表示[0,n]之间最小的不能表示的值,我们将它初始化为1,如果将它初始化为0的话,没有意义。那么此时我们能表示的范围是[0, miss),表示此时我们能表示0到miss-1的数,如果此时的num <= miss,那么我们可以把我们能表示数的范围扩大到[0, miss+num),如果num > miss,那么此时我们需要添加一个数,为了能最大限度的增加表示数范围,利用贪心的思想,我们加上miss它本身
(1) Greedy
1
class Solution {
2
public int minPatches(int[] nums, int n) {
3
long miss = 1;
4
int count = 0;
5
int index = 0;
6
7
while (miss <= n) {
8
if (index < nums.length && nums[index] <= miss) {
9
miss += nums[index];
10
++index;
11
}
12
else {
13
miss += miss;
14
++count;
15
}
16
}
17
return count;
18
}
19
}
Copied!

3. Time & Space Complexity

Greedy: 时间复杂度O(n), 空间复杂度O(1)