ChunNote
0%

leetCode-330:Patching Array

发表于 分类于

问题描述

给定一个升序的整数数组和一个整数 n，要求往数组中添加元素，使得 1~n 中的数字都能由数组中的一个或多个元素的总和构成，要求输出添加元素的最小个数。题目链接：点我

样例输入输出

输入：nums = [1,3], n = 6

输出：1

解释：添加2，数组构成：[1,2,3]。数字 1 由 [1] 构成，数字 2 由 [2] 构成，数字 3 由 [1,2] 构成，数字 4 由 [1,3] 构成，数字 5 由 [2,3] 构成，数字 6 由 [1,2,3] 构成

输入：nums = [1,5,10], n = 20

输出：2

解释：添加 2，4

问题解法

此题解法参考：https://leetcode.cn/problems/patching-array/solution/an-yao-qiu-bu-qi-shu-zu-by-leetcode-solu-klp1。主要做法是：由 1 开始构造连续区间直到 n，构造过程中如果区间已经包含了数组的元素，则将数组下标往后移动，如果没有包含，则将区间扩大一倍。其依赖的原理如下：如果 1~m 是一个连续的区间，那由其中的数字进行组合可以得到 1~2m-1 的连续区间。因为在 1~m-1的数字分别加上 m 就能得到 m+1~2m-1的区间，结合前面的 1~m 就是 1~2m-1。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int minPatches(int[] nums, int n) {
        int count = 0;
        int i = 0;
        long current = 1;
        while (current <= n) {
            if (i < nums.length && nums[i] <= current) {
                current += nums[i];
                i++;
            } else {
                current *= 2;
                count++;
            }
        }
        
        return count;
    }
}

参考资料

https://leetcode.cn/problems/patching-array/solution/an-yao-qiu-bu-qi-shu-zu-by-leetcode-solu-klp1