leetcode算法題答案PDF，每日算法系列【LeetCode 330】按要求補齊數組

題目描述

給定一個已排序的正整數數組 nums ，和一個正整數 n 。從 [1, n] 區間內選取任意個數字補充到 nums 中，使得 [1, n] 區間內的任何數字都可以用 nums 中某幾個數字的和來表示。請輸出滿足上述要求的最少需要補充的數字個數。

示例1

        輸入：
nums = [1,3], n = 6
輸出：
1
解釋：
根據 nums 里現有的組合 [1], [3], [1,3]，可以得出 1, 3, 4。
現在如果我們將 2 添加到 nums 中， 組合變為: [1], [2], [3], [1,3], [2,3], [1,2,3]。
其和可以表示數字 1, 2, 3, 4, 5, 6，能夠覆蓋 [1, 6] 區間里所有的數。
所以我們最少需要添加一個數字。

leetcode算法題答案PDF、 示例2

        輸入：
nums = [1,5,10], n = 20
輸出：
2
解釋：
我們需要添加 [2, 4]。

示例3

        輸入：
nums = [1,2,2], n = 5
輸出：
0

題解

首先這題沒有說數據范圍，根據正解的時間復雜度，推測出 nums.length 的大小在 1e5 左右，而 n 的大小在 int 的最大值左右。

leetcode 快速排序。而不考慮數據范圍，我剛開始的想法是，首先考慮簡化問題：用 nums 數組中的數字可以表示出多少個不同的正整數？ 這可以用動態規劃來解決，令 dp[S][i] 表示用前 i 個數湊出和 S 是否可行，那么狀態轉移方程就是： dp[S][i] = dp[S-nums[i]][i-1] || dp[S][i-1] 。 然后遍歷 dp[i][nums.length-1] ，如果發現等于 0 ，就說明 nums 數組無法湊出 i 這個和，于是新增加一個數 i ，并且將 [i, 2i)中的所有 dp 值都改成 1，直到 [1, n] 全部被覆蓋了。 后來看了才發現，我弱智了，這樣不僅沒必要，而且 n 太大會炸裂。

正解很簡單。首先題目中有個詞“已排序”，其實不是很重要，沒排序的話我排個序也不怎么耗時間。那排完序怎么辦呢，思路還是剛剛的思路，只是不用動態規劃了。

試想從最小的 1 開始，如果 1 不在數組里，那一定要補上一個 1 的，然后 [1, 2) 范圍里的數都可以被表示出來了。然后看下一個數，如果大于 2 ，那么 2 是沒有辦法通過數組里的數表示出來的，因為比它小的數只能湊出 [1, 2) ，所以 2 也要補上。如果下一個數小于等于 2 ，那么我們可以利用目前的數湊出 [1, 4) 里面的數，然后繼續往下遍歷，直到能夠湊出 [1, n+1) 里面的數。

無序數組查找最優算法。一般情況下，如果遍歷到 nums[i-1] 時，可以表示出 [1, S) 范圍內的數，那么如果 nums[i] > S ，那么需要補上 S ，并且可表示范圍更新為 [1, 2S)，然后繼續看 nums[i] ；否則的話可表示范圍更新為 [1, S+nums[i]) ，然后看 nums[i+1] 就行了。

這樣就比原來的思路簡化了很多了，那么時間復雜度怎么樣呢？ 因為 S 每次更新有兩種情況，要么乘以 2 ，要么加上了 nums[i] ，所以最終時間復雜度是 。

代碼

c++

        class Solution {
public:int minPatches(vector<int>& nums, int n) {int len = nums.size(), idx = 0, res = 0;long long r = 1;while (r <= n) {if (idx < len && nums[idx] <= r) {r += nums[idx++];} else {res++;r += r;}}return res;}
};

python

        class Solution:def minPatches(self, nums: List[int], n: int) -> int:length = len(nums)idx = res = 0r = 1while r <= n:if idx < length and nums[idx] <= r:r += nums[idx]idx += 1else:res += 1r += rreturn res