每日一题：按要求补齐数组

题意

给定一个已排序的正整数数组 $nums$，和一个正整数 $n$ 。从 $[1, n]$ 区间内选取任意个数字补充到 $nums$ 中，使得 $[1, n]$ 区间内的任何数字都可以用 $nums$ 中某几个数字的和来表示。请输出满足上述要求的最少需要补充的数字个数。

Soluiton

容易证明，对于正整数 $x$，如果区间 $[1,x−1]$ 内的所有数字都已经被覆盖，且 $x$ 在数组中，则区间 $[1,2x−1]$ 内的所有数字也都被覆盖。

由此可以提出一个贪心的方案。每次找到未被数组 $nums$ 覆盖的最小的整数 $x$，在数组中补充 $x$，然后寻找下一个未被覆盖的最小的整数，重复上述步骤直到区间 $[1,n]$ 中的所有数字都被覆盖。

具体实现：

$x$ 表示当前能表示出 $[1, x - 1]$ 的所有数字，初始化为 $1$，枚举数组。

• 若枚举到的数小等于 $x$，则加上，表示能表示出 $[1, x + num[i] - 1]$ 的所有数字，然后下标加 $1$
• 若枚举到的数大于 $x$，则说明 $x$ 无法被表示出来，我们需要增加一个数 $x$，然后$x$ 加上 $x$，表示能表示出 $[1, x + x - 1]$ 的所有数字

Code

class Solution {
public:
    int minPatches(vector<int>& a, int n) {
        long x = 1;
        int res = 0, i = 0, m = a.size();
        while (x <= n) {
            if (i < m && a[i] <= x) {
                x += a[i];
                i++;
            } else {
                x *= 2;
                res++;
            }
        }
        return res;
    }
};