花期内花的数目_flower[i]表示第i朵鲜花第i次需要查询第idx朵鲜花和类型为type鲜花之间的最小距离

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

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

链接：https://leetcode.cn/problems/number-of-flowers-in-full-bloom

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

思路

1、哈希表+差分数组+前缀和
2、二分查找

代码

class Solution {
public:
    vector<int> fullBloomFlowers(vector<vector<int>>& flowers, vector<int>& persons) {

        // 暴力方法时间复杂度为O(n2)
        // 方法一、建立一个数组，该数组表示对应时刻花的数目
        // 告诉了区间端点，考虑使用差分数组，差分数组的初始值为0
        // 差分+哈希表+前缀和
        // 差分的前缀和就是原数组
        // 对应区间[i,j]增加a，差分数组mp[i]+=a,mp[j+1]-=a

        // map<int,int> mp;

        // for(auto& flower:flowers){
        //     mp[flower[0]]+=1;
        //     mp[flower[1]+1]-=1;
        // }

        // for(auto person:persons) mp[person];

        // int sum=0;
        // for(auto &[x,y]:mp){
        //     sum+=y;
        //     y=sum;
        // }

        // for(auto& person:persons)
        // person=mp[person];

        // return persons;

        // 方法二、使用二分查找，基于在某时刻看到的花，等于早于或者等于该时刻开放的花的数量减去早于该时刻结束的花的数量

        // 对应upper_bound()、lower_bound()

        vector<int> a;
        vector<int> b;

        for(vector<int>& flower:flowers){
            a.push_back(flower[0]);
            b.push_back(flower[1]);
        }

        sort(a.begin(),a.end());
        sort(b.begin(),b.end());

        vector<int> ans(persons.size());

        for(int i=0;i<persons.size();i++){

            ans[i]=upper_bound(a.begin(),a.end(),persons[i])-a.begin()-(lower_bound(b.begin(),b.end(),persons[i])-b.begin());
        }

        return ans;

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57