当前位置：网站首页>【二分查找-简单】LCP 18. 早餐组合

【二分查找-简单】LCP 18. 早餐组合

2022-04-21 15:08:00 【菜菜2022】

题目
注意：答案需要以 1e9 + 7 (1000000007) 为底取模，如：计算初始结果为：1000000008，请返回 1
提示：

1 <= staple.length <= 10^5
1 <= drinks.length <= 10^5
1 <= staple[i],drinks[i] <= 10^5
1 <= x <= 2*10^5

【代码】
执行用时：1064 ms, 在所有 Python3 提交中击败了11.97% 的用户
内存消耗：28.6 MB, 在所有 Python3 提交中击败了96.95% 的用户
通过测试用例：65 / 65

class Solution:
    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:
        ans=0
        staple.sort()
        drinks.sort()
        for item in staple:
            #寻找drinks中从左到右 第一个大于>x-item的 数字下标
            if x-item<=0:
                continue
            left,right=0,len(drinks)-1
            while left<=right:
                mid=left+(right-left)//2
                if drinks[mid]<=(x-item):
                    left=mid+1
                else:
                    right=mid-1
            ans+=left
        return ans%(10**9 + 7 )

版权声明
本文为[菜菜2022]所创，转载请带上原文链接，感谢
https://blog.csdn.net/kz_java/article/details/124272457

边栏推荐

猜你喜欢

随机推荐