到底谁会在周日早上刷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
}