330 Patching Array

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

class Solution {
    public int minPatches(int[] nums, int n) {
        long miss = 1;
        int count = 0;
        int index = 0;

        while (miss <= n) {
            if (index < nums.length && nums[index] <= miss) {
                miss += nums[index];
                ++index;
            }
            else {
                miss += miss;
                ++count;
            }
        }
        return count;
    }
}

3. Time & Space Complexity

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