給出一個數(shù)列spells和一個數(shù)列potions,用spells里面每個數(shù)依次乘以potions里面每個數(shù),輸出和spells等長的數(shù)列,每個值等于用spells里面每個數(shù)乘以potions每個數(shù)得到的length(potions)個數(shù)里面大于等于給定值success的數(shù)量
先對potions按從小到大排序,然后對于spells里面每個數(shù),二分第一個符合大于等于success的數(shù)的位置
注意邊界值
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