需要添加的硬币的最小数量
题目要求：
解题思路
为方便描述，把 0 也算作可以得到的数。
假设现在得到了区间 [ 0 , s − 1 ] [0,s−1] [0,s−1] 中的所有整数，如果此时遍历到整数 x = c o i n s [ i ] x=coins[i] x=coins[i]，那么把 [ 0 , s − 1 ] [0,s−1] [0,s−1] 中的每个整数都增加 x x x，我们就得到了区间 [ x , s + x − 1 ] [x,s+x−1] [x,s+x−1] 中的所有整数。
思路
把
c
o
i
n
s
coins
coins 从小到大排序，遍历
x
=
c
o
i
n
s
[
i
]
x=coins[i]
x=coins[i]。分类讨论，看是否要添加数字：
- 如果 x ≤ s x \le s x≤s，那么合并 [ 0 , s − 1 ] [0,s−1] [0,s−1] 和 [ x , s + x − 1 ] [x,s+x−1] [x,s+x−1] 这两个区间，我们可以得到 [ 0 , s + x − 1 ] [0,s+x−1] [0,s+x−1] 中的所有整数。
- 如果 x > s x>s x>s，或者遍历完了 c o i n s coins coins 数组，这意味着我们无法得到 s s s，那么就一定要把 s s s 加到数组中（加一个比 s s s 还小的数字就没法得到更大的数，不够贪），这样就可以得到了 [ s , 2 s − 1 ] [s,2s−1] [s,2s−1] 中的所有整数，再与 [ 0 , s − 1 ] [0,s−1] [0,s−1] 合并，可以得到 [ 0 , 2 s − 1 ] [0,2s−1] [0,2s−1] 中的所有整数。然后再考虑 x x x 和 2 s 2s 2s 的大小关系，继续分类讨论。
当 s > t a r g e t s s>targets s>targets时，我们就得到了 [ 1 , t a r g e t ] [1,target] [1,target] 中的所有整数，退出循环。
代码
class Solution:
def minimumAddedCoins(self, coins: List[int], target: int) -> int:
coins.sort()
ans, s, i = 0,1,0
while s<= target:
if i<len(coins) and coins[i]<=s:
s += coins[i]
i+=1
else:
s *= 2
ans +=1
return ans
复杂度分析
- 时间复杂度：
O
(
n
l
o
g
n
+
l
o
g
t
a
r
g
e
t
)
O(nlogn+logtarget)
O(nlogn+logtarget)，其中
n
n
n 为
c
o
i
n
s
coins
coins 的长度。
s
s
s 至多翻倍
O
(
l
o
g
t
a
r
g
e
t
)
O(logtarget)
O(logtarget) 次。瓶颈主要在排序上。
空间复杂度： O ( 1 ) O(1) O(1)。忽略排序的栈开销。
参考
灵茶山艾府
