给出一个数列spells和一个数列potions,用spells里面每个数依次乘以potions里面每个数,输出和spells等长的数列,每个值等于用spells里面每个数乘以potions每个数得到的length(potions)个数里面大于等于给定值success的数量
先对potions按从小到大排序,然后对于spells里面每个数,二分第一个符合大于等于success的数的位置
注意边界值
1 #2300
2 #Runtime: 1082 ms (Beats 100%)
3 #Memory: 37.5 MB (Beats 38.71%)
4
5 class Solution(object):
6 def successfulPairs(self, spells, potions, success):
7 """
8 :type spells: List[int]
9 :type potions: List[int]
10 :type success: int
11 :rtype: List[int]
12 """
13 potions.sort()
14 ans = []
15 for sp in spells:
16 ans.append(len(potions) - bisect_left(potions, ceil(1.0 * success / sp)))
17 return ans