1 public class Solution { 2 public int minPatches(int[] nums, int n) { 3 long missed = 1; 4 int index = 0; 5 int result = 0; 6 while (missed <= n) { 7 if (index < nums.length && nums[index] <= missed) { 8 missed += nums[index++]; 9 } else {10 missed += missed;11 result++;12 }13 }14 return result;15 }16 } 这个代码简单但逻辑深刻。它的工作原理如下:
1. 从[1, n]这个范围开始寻找。当你找到一个数在数组中小于当前missed时，将这个数加到missed上，并且将这个数从数组中移除。这样就能形成一个新的范围[1, missed + nums[i]]。
2. 如果没有找到符合条件的数，那么最好的选择是将missed自身加到missed上。因为在之前的步骤中，我们已经能够形成一个[1, missed)的范围。为什么不能直接加一个更大的数呢？
举个例子来理解这个逻辑。如果你有一个范围[1, missed)，再加一个数x。你的目标是形成一个新的范围[1, missed + x)。在这种情况下，missed是最大的缺失数。当前的数无法覆盖到这个missed本身，因此只能选择将missed加到自身。
转载自:https://www.cnblogs.com/shuashuashua/p/5633442.html
