bgm

***

2251. 花期内花的数目

给你一个下标从 0 开始的二维整数数组 flowers ，其中 flowers[i] = [starti, endi] 表示第 i 朵花的 花期 从 starti 到 endi （都 包含）。同时给你一个下标从 0 开始大小为 n 的整数数组 people ，people[i] 是第 i 个人来看花的时间。

请你返回一个大小为 n 的整数数组 answer ，其中 answer[i]是第 i 个人到达时在花期内花的 数目 。

示例 1：

输入：flowers = [[1,6],[3,7],[9,12],[4,13]], people = [2,3,7,11]
输出：[1,2,2,2]
解释：上图展示了每朵花的花期时间，和每个人的到达时间。
对每个人，我们返回他们到达时在花期内花的数目。

示例 2：

输入：flowers = [[1,10],[3,3]], people = [3,3,2]
输出：[2,2,1]
解释：上图展示了每朵花的花期时间，和每个人的到达时间。
对每个人，我们返回他们到达时在花期内花的数目。

提示：

1 <= flowers.length <= 5 * 10^4
flowers[i].length == 2
1 <= starti <= endi <= 10^9
1 <= people.length <= 5 * 10^4
1 <= people[i] <= 10^9

模拟

1
2
3
4
5
6
7
8
class Solution:
    def fullBloomFlowers(self, flowers: List[List[int]], people: List[int]) -> List[int]:
        sum=[0]*len(people)
        for i in range(len(people)):
            for j in range(len(flowers)):
                if people[i]<=flowers[j][1] and people[i]>=flowers[j][0]:
                    sum[i]+=1
        return sum

超时45 / 52 个通过的测试用例

先排序再整个bisect什么的

1
2
3
4
5
6
7
8
9
10
class Solution:
    def fullBloomFlowers(self, flowers: List[List[int]], people: List[int]) -> List[int]:
        n=len(people)
        sum=[0]*n
        st=sorted(s for s,e in flowers)
        ed=sorted(e for s,e in flowers)
        for i in range(n):
            k=people[i]
            sum[i]=bisect_right(st,k)-bisect_left(ed,k)
        return sum

192ms,39.3mb,差不多啦

bisect啥玩意的用法

是py内置二分查找

bisect 模块中最常用的方法是 bisect()，查找一个元素在有序列表中应该插入的位置。这个方法采用二分查找的方式，所以是logn

1
2
3
4
5
6
7
8
9
10
import bisect


my_list = [1, 3, 5, 7, 9]

bisect.insort(my_list, 4)
print(my_list)  #  [1, 3, 4, 5, 7, 9]

position = bisect.bisect(my_list, 6)
print(position)  #  4

其他

  • bisect_left()：返回这个元素的最左边，[1,2,2,2,2,2,3],返回第一个2位置

  • bisect_right()：返回比他大的，也就是上图的第一个3位置

  • bisect_left() 和 bisect_right() 的组合查找符合条件的元素的范围

  • 不实际插入