本文主要是介绍【C++离线查询】2250. 统计包含每个点的矩形数目，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
本文涉及的基础知识点
离线查询
LeetCode2250. 统计包含每个点的矩形数目
给你一个二维整数数组 rectangles ，其中 rectangles[i] = [li, hi] 表示第 i 个矩形长为 li 高为 hi 。给你一个二维整数数组 points ，其中 points[j] = [xj, yj] 是坐标为 (xj, yj) 的一个点。
第 i 个矩形的 左下角 在 (0, 0) 处，右上角 在 (li, hi) 。
请你返回一个整数数组 count ，长度为 points.length，其中 count[j]是 包含 第 j 个点的矩形数目。
如果 0 <= xj <= li 且 0 <= yj <= hi ，那么我们说第 i 个矩形包含第 j 个点。如果一个点刚好在矩形的 边上 ，这个点也被视为被矩形包含。
示例 1：
输入：rectangles = [[1,2],[2,3],[2,5]], points = [[2,1],[1,4]]
输出：[2,1]
解释：
第一个矩形不包含任何点。
第二个矩形只包含一个点 (2, 1) 。
第三个矩形包含点 (2, 1) 和 (1, 4) 。
包含点 (2, 1) 的矩形数目为 2 。
包含点 (1, 4) 的矩形数目为 1 。
所以，我们返回 [2, 1] 。
示例 2：
输入：rectangles = [[1,1],[2,2],[3,3]], points = [[1,3],[1,1]]
输出：[1,3]
解释：
第一个矩形只包含点 (1, 1) 。
第二个矩形只包含点 (1, 1) 。
第三个矩形包含点 (1, 3) 和 (1, 1) 。
包含点 (1, 3) 的矩形数目为 1 。
包含点 (1, 1) 的矩形数目为 3 。
所以，我们返回 [1, 3] 。
提示：
1 <= rectangles.length, points.length <= 5 * 104
rectangles[i].length == points[j].length == 2
1 <= li, xj <= 109
1 <= hi, yj <= 100
所有 rectangles 互不相同 。
所有 points 互不相同 。
C++二分查找
注意：y和高度<=100，故可以不用树状数组。
将rectangles按宽的降序排序
将points的下标indexs按x降序排序。
枚举indexs。
ys[j]记录矩形宽度大于等于points[i][0]且高度为j的矩形数量。
去掉排序的时间复杂度为：O(n100)
代码
核心代码
class Solution {public:vector<int> countRectangles(vector<vector<int>>& rectangles, vector<vector<int>>& points) {sort(rectangles.begin(), rectangles.end(), [&](const auto& v1, const auto& v2) {return v1[0] > v2[0]; });vector<int> indexs(points.size());iota(indexs.begin(), indexs.end(), 0);sort(indexs.begin(), indexs.end(), [&](int i1, int i2) {return points[i1][0] > points[i2][0]; });int ys[101] = { 0 };int j = 0;vector<int> ret;for (const auto& iiii : indexs) {while ((j < rectangles.size()) && (rectangles[j][0] >= points[iiii][0])) {ys[rectangles[j][1]]++;j++;}int cur = 0;for (int k = points[iiii][1]; k <= 100; k++) {cur += ys[k];}ret.emplace_back(cur);}return ret;}};
单元测试
vector<vector<int>>rectangles, points;TEST_METHOD(TestMethod11){rectangles = { {1,2},{2,3},{2,5} }, points = { {2,1},{1,4} };auto res = Solution().countRectangles(rectangles, points);AssertEx({ 2,1 }, res);}TEST_METHOD(TestMethod12){rectangles = { {1,1},{2,2},{3,3} }, points = { {1,3},{1,1} };auto res = Solution().countRectangles(rectangles, points);AssertEx({1,3 }, res);}
扩展阅读
| 我想对大家说的话 |
|---|
| 工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。 |
| 学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作 |
| 有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注 |
| 闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
| 失败+反思=成功 成功+反思=成功 |
视频课程
先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
这篇关于【C++离线查询】2250. 统计包含每个点的矩形数目的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
