二分查找|差分数组|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 * 10⁴
flowers[i].length == 2
1 <= starti <= endi <= 10⁹
1 <= people.length <= 5 * 10⁴
1 <= people[i] <= 109

二分查找

时间复杂度

O(nlogn)。

原理

用向量分别记录开始时间starti和结束时间endi+1，并排序。通过二分查找，可以获取早于等于某个时间开始（结束）的花的数量。已经开花的数量减结束开花的数量。下面讨论时刻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);

}

离散化差分数组

变量解析

代码

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