本文主要是介绍二分查找|差分数组|LeetCode2251:花期内花的数目，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
作者推荐
贪心算法LeetCode2071:你可以安排的最多任务数目
本文涉及的基础知识点
二分查找算法合集
题目
给你一个下标从 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;
}
};
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 我想对大家说的话 |
|---|
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业 |
。也就是我们常说的专业的人做专业的事。 |
|如果程序是一条龙，那算法就是他的是睛|
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境：
VS2022 C++17
这篇关于二分查找|差分数组|LeetCode2251:花期内花的数目的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
