[LeetCode]Patching Array

乍看之下可能没有什么思路，但是让我们从base case开始慢慢分析。我们用arr来表示patch之后的数组，我们可以从k = 1开始一直计算到n = k的时候arr应该包含什么元素，从而推出给定数组nums缺少什么元素。为了实现这个算法，我们维护当前我们扫过的nums的元素和patch过的元素的和所在的区间的上界hi，下界一直都是1我们不需要维护。这个区间显然是连续的，因为我们发现不连续的情况会patch。当我们：

1. 发现当前元素nums[i] > hi + 1，表明当前出现了gap，我们需要添加元素来抹平。那么我们应该添加什么元素呢？很显然是hi + 1，添加其他任何数都不可能填补hi + 1的gap，然而添加hi + 1之后我们可以把区间扩张到[1, 2 * hi + 1]，因为之前我们扫过和patch过得所有元素的和的上界是hi，那么添加了hi + 1之后上界会变成hi + hi + 1
2. 发现当前元素nums[i] <= hi，表明没有出现gap，那么我们多了一个元素nums[i]，用其更新上界即可，更新后区间会变为[1, nums[i] + hi]
3. 发现i >= nums[len]，同样代表出现了gap，处理情况同1

我们重复上述步骤直到hi >= n即可，时间复杂度O(k)，k为完整数组arr的长度，常数空间，代码如下：

	class Solution {
	public:
	int minPatches(vector<int>& nums, int n) {
	if(n < 1)return 0;
	int count = 0, len = nums.size(), i = 0;
	long hi = 0;
	while(hi < n)
	{
	if(i >= len || nums[i] > hi + 1)
	{
	++count;
	hi = 2 * hi + 1;
	}
	else
	{
	hi = nums[i] + hi;
	++i;
	}
	}
	return count;
	}
	};

view raw Patching Array.cpp hosted with ❤ by GitHub