到底誰會在周日早上刷leetcode
330. Patching Array
有一個由小到大排序的array:nums
以及一個整數n
請問最少要往nums裡面插入幾個數字
才可以用nums裡的元素組合出1~n之間的所有元素?
思路:
假設cur是到nums[i]可以組合出的最大範圍1~cur
這時候如果nums[i+1]不是cur+1
就要想辦法組合出cur+1~nums[i+1]之間的元素
舉例來說:[1、2、10]
1、2可以組合出1~3之間的所有數
而第三個元素是10，所以你要想辦法湊出4~9
最直接的方法就是先加入4，這時你就可以組合出1~3+4
還缺8、9，所以再加入8，就可以組合出1~3+4+8
可以得出一個判斷式，當你的nums[i+1]>cur+1時
你就要插入cur+1，一直到nums[i+1]<=cur+1或是cur>=n
這樣就可以得到答案了
golang code：
func minPatches(nums []int, n int) int {
cur, ans, l := 0, 0, len(nums)
for i := 0; i < l; i++ {
for nums[i] > cur+1 {
cur += cur + 1
ans++
if cur >= n {
return ans
}
}
cur += nums[i]
if cur >= n {
return ans
}
}
for cur < n {
cur += cur + 1
ans++
}
return ans
}