题目描述
给你一个整数数组 coins
表示不同面额的硬币,另给你一个整数 k
。
你有无限量的每种面额的硬币。但是,你 不能 组合使用不同面额的硬币。
返回使用这些硬币能制造的 第 kth 小 金额。
思路
在学习完丑数系列之后再回顾这道题,其实是 1201. 丑数 III 的扩展,1201 这道题只有三个数字,而这道题有 len(coins)<=15
个数字。实际上我们并不需要改 1201 的太多代码,修改 check
函数即可,那该怎么修改呢?
假设 coins = [a, b]
,那么情况为:
ugly(x)=ax+bx−a×bx
假设 coins = [a,b,c]
,情况为:
ugly(x)=ax+bx+cx−a×bx−a×cx−b×cx+a×b×cx
可以看到,对于 n
个硬币一共会有 2n−1 种情况,我们可以想到用位运算来计算:
假设 n=3
,那么可以分成以下几种情况:
001, 010, 100
对应 ax+bx+cx;
011, 101, 110
对应 −a×bx−a×cx−b×cx;
111
对应 a×b×cx。
这是很显而易见的。那么我们遍历 range(1, 1<<len(coins))
,再去根据位数去 coins
中取数据即可实现 check
函数:
接下来开始二分搜索,左右范围怎么取呢?左边可以取 1,那最大的值该取多少呢?假设 coins
中的最小值为 min(coins)
,那么最坏情况下 min(coins)*k
一定满足要求。
这样就可以写出最终代码:
优化:在 check
函数中我们进行了太多重复的计算,这一段可以缓存以提高速度。
想得太多
错误的想法
最开始是想统计数字的最小公倍数,然后获取这里面的所有数字并排序,第 k 小金额就是先整除所有数字再去取模数的值:
OOM 了,想必是
这一段造成的。
结果发现是自己已经忘了容斥原理了,这下尴尬了。