題目描述

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

示例1

輸入： nums = [1,3], n = 6 輸出： 1 解釋： 根據(jù) nums 里現(xiàn)有的組合 [1], [3], [1,3]，可以得出 1, 3, 4。 現(xiàn)在如果我們將 2 添加到 nums 中， 組合變?yōu)? [1], [2], [3], [1,3], [2,3], [1,2,3]。 其和可以表示數(shù)字 1, 2, 3, 4, 5, 6，能夠覆蓋 [1, 6] 區(qū)間里所有的數(shù)。 所以我們最少需要添加一個(gè)數(shù)字。

示例2

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

示例3

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

題解

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

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

正解很簡單。首先題目中有個(gè)詞“已排序”，其實(shí)不是很重要，沒排序的話我排個(gè)序也不怎么耗時(shí)間。那排完序怎么辦呢，思路還是剛剛的思路，只是不用動(dòng)態(tài)規(guī)劃了。

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

一般情況下，如果遍歷到 nums[i-1] 時(shí)，可以表示出 [1, S) 范圍內(nèi)的數(shù)，那么如果 nums[i] > S ，那么需要補(bǔ)上 S ，并且可表示范圍更新為 [1, 2S)，然后繼續(xù)看 nums[i] ；否則的話可表示范圍更新為 [1, S+nums[i]) ，然后看 nums[i+1] 就行了。

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

。

代碼

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 與50位技術(shù)專家面對面20年技術(shù)見證，附贈(zèng)技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的如何表示数组所有数都不等于一个数_每日算法系列【LeetCode 330】按要求补齐数组...的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。