[LeetCode][Hard] Patching Array 按要求补齐数组 | Java

问题

Patching Array Hard

Given a sorted integer array nums and an integer n, add/patch elements to the array such that any number in the 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:

Input: nums = [1,3], n = 6
Output: 1
Explanation:
Combinations of nums are [1], [3], [1,3], which form possible sums of: 1, 3, 4.
Now if we add/patch 2 to nums, the combinations are: [1], [2], [3], [1,3], [2,3], [1,2,3].
Possible sums are 1, 2, 3, 4, 5, 6, which now covers the range [1, 6].
So we only need 1 patch.

Example 2:

Input: nums = [1,5,10], n = 20
Output: 2
Explanation: The two patches can be [2, 4].

Example 3:

Input: nums = [1,2,2], n = 5
Output: 0

 

Constraints:

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 10^4
• nums is sorted in ascending order.
• 1 <= n <= 2^31 - 1

解题思路

本题给定一个有序的数组nums和一个自然数n，要求用数组中的任意一个或多个元素之和来表示从1到n的所有数字。为了达到这个目的，可以往数组里面添加元素。问最少添加几个元素才能达到目的？

按照常规思维，我们可能会这么做：

1. 列出既定数组中所有可能的元素组合，并将这些组合的和放入一个集合中
2. 从1到n逐个判断是否包含在上述集合中
3. 若不在集合中，则添加对应的数字到数组nums中

这个解法看似可行，但实际上已经掉到陷阱里了。仔细看看题目的约束可以发现，n <= 2^31 - 1，如果试图创建一个大小为2^31 - 1的集合，会直接导致内存溢出。也就是说此路不通，不能试图将数组nums中最终的元素逐个列举出来。我们需要找到一种数学计算的方式来解决该问题。

我们需要改变一下思维，不要试图从nums推导处1到n，而是反过来逆向思考一下，假定我们已经知道nums中的元素之和可以表示从[1，m)的数字（不包含m），若此时我们往nums中添加一个数k，那么数组可以表示的自然数区间会有什么变化吗？答案是可表示的区间变成了[1, m)和[1+k, m+k)的并集，如果k <= m，那么并集就可以合并为[1, m+k)。如果k > m，则不能合并，从而导致可表示的区间不连续，所以需要先将m添加到数组，让可表示的区间扩展为[1, m+m)，然后在继续对k进行处理。如果想通了这一点，这道题就完成了一半。

假设用miss表示[1, n]中最小的可能缺失的数字（即不能用数组元素的和来表示的数字，对应上文中的m），那么也就是说[1, miss)（不包含miss）已经可以用数组元素的和来表示。

1. 我们将miss的初始值设为1，然后遍历数组nums。
2. 如果出现数组中的某个元素nums[i] <= miss，则可表示的区间可以扩展为[1, nums[i] + miss)，然后继续处理下一个元素。
3. 如果nums[i] > miss，则需要将miss加入到数组，可表示的区间可以扩展为[1, miss + miss)，此时将miss的值设为miss + miss，再回到步骤2中，对nums[i]进行判断。
4. 统计将miss加入到数组的次数，就是最终答案。

本题的解答参考了StefanPochmann大神的方案。

参考答案

public class Solution {

    public int minPatches(int[] nums, int n) {
        long miss = 1;
        int ret = 0;
        int i = 0;

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

拓展训练

到作者的LeetCode专栏中看看，有没有其他感兴趣的问题吧！

资料链接

原题 leetcode.com/problems/pa…

StefanPochmann的解决方案 leetcode.com/problems/pa…