作者推荐
本文涉及的基础知识点
题目
给你一个下标从 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 * 104
flowers[i].length == 2
1 <= starti <= endi <= 109
1 <= people.length <= 5 * 104
1 <= people[i] <= 109
二分查找
时间复杂度
O(nlogn)。
原理
用向量分别记录开始时间starti和结束时间endi+1，并排序。通过二分查找，可以获取早于等于某个时间开始（结束）的花的数量。已经开花的数量减结束开花的数量。下面讨论时刻t。
| 开始时间小于等于t | 结束时间小于等于t | 看不到，花期已结束 |
| 开始时间小于等于t | 结束时间大于t | 可以看到 |
| 开始时间大于t | 结束时间小于等于t | 不存在 |
| 开始时间大于t | 结束时间大于t | 看不到，花期未开始 |
情况三不存在，情况一和情况四相互抵消。
核心代码
class Solution { public: vector<int> fullBloomFlowers(vector<vector<int>>& flowers, vector<int>& people) { vector<int> vStart, vEnd; for (const auto& v : flowers) { vStart.emplace_back(v[0]); vEnd.emplace_back(v[1] + 1); } sort(vStart.begin(), vStart.end()); sort(vEnd.begin(), vEnd.end()); vector<int> vRet; for (const auto& peo : people) { const int iHasStartCount = std::upper_bound(vStart.begin(), vStart.end(), peo)- vStart.begin(); const int iHasEndCount = std::upper_bound(vEnd.begin(), vEnd.end(), peo) - vEnd.begin(); vRet.emplace_back(iHasStartCount - iHasEndCount); } return vRet; } };
测试用例
template void Assert(const vector& v1, const vector& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { assert(v1[i] == v2[i]); } } template void Assert(const T& t1, const T& t2) { assert(t1 == t2); } int main() { int n; vector<vector> flowers; vector people,res; { Solution slu; flowers = { {1, 6}, {3, 7}, {9, 12}, {4, 13} }, people = { 2, 3, 7, 11 }; auto res = slu.fullBloomFlowers(flowers, people); Assert(vector{1, 2, 2, 2}, res); } { Solution slu; flowers = flowers = { {1,10},{3,3} }, people = { 3,3,2 }; auto res = slu.fullBloomFlowers(flowers, people); Assert(vector{2,2,1}, res); }
//CConsole::Out(res);
}
离散化差分数组
变量解析
| mDiffOpe | 记录花期的变化，key时间，value花期的变化数量，花期开始+1，花期结束-1 |
| mDiffNum | 时间对应的花数，只记录花期发生变化的日期 |
代码
class Solution { public: vector fullBloomFlowers(vector<vector>& flowers, vector& persons) { std::map<int, int> mDiffOpe, mDiffNum; for (const auto& v : flowers) { mDiffOpe[v[0]]++; mDiffOpe[v[1] + 1]–; } int iNum = 0; for (const auto& it : mDiffOpe) { iNum += it.second; mDiffNum[it.first] = iNum; } mDiffNum[0] = 0; vector vRet; for (const auto& per : persons) { auto it = mDiffNum.upper_bound(per); vRet.emplace_back((–it)->second); } return vRet; } };
。也就是我们常说的专业的人做专业的事。 |
|如果程序是一条龙，那算法就是他的是睛|
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境：
VS2022 C++17
