本文涉及的基础知识点

离线查询

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 * 10⁴

rectangles[i].length == points[j].length == 2

1 <= li, xj <= 10⁹

1 <= hi, yj <= 100

所有 rectangles 互不相同 。

所有 points 互不相同 。

C++二分查找

注意：y和高度<=100，故可以不用树状数组。

将rectangles按宽的降序排序

将points的下标indexs按x降序排序。

枚举indexs。

ys[j]记录矩形宽度大于等于points[i][0]且高度为j的矩形数量。

去掉排序的时间复杂度为：O(n100)

代码

核心代码

<code>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++**实现。