统计包含每个点的矩形数目

标签: 树状数组 数组 二分查找 排序

难度: Medium

给你一个二维整数数组 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 互不相同 。

Submission

运行时间: 176 ms

内存: 35.4 MB

"""
binary search
T: O(nmlogC)
S: O(1)
the number of rectangles that contain the jth point is a decreasing array w.r.t l and h
so we can use binary search
"""
class Solution:
    def countRectangles(self, rectangles: List[List[int]], points: List[List[int]]) -> List[int]:
        m, n = len(rectangles), len(points)
        ans = [0] * n 

        # 1. O(mlogm) sort ractangles array by height descendingly
        rectangles.sort(key=lambda x: -x[1])

        # 2. O(mlogm) sort points array by height descendingly
        points_indices = sorted(range(n), key=lambda j: -points[j][1])

        # 3. O(n) iterates over sorted points array
        i = 0   # pointer iterates over sorted ractangles array
        rect_xs = []    # x-coordinates of all the rectangles with hi >= yj
        for j in points_indices:
            x, y = points[j]

            # iterates over sorted ractangles array, store x-coordinates of all the rectangles with hi >= yj
            start = i 
            while i < m and rectangles[i][1] >= y:
                rect_xs.append(rectangles[i][0])
                i += 1

            # sort rect_xs array ascendingly
            if i > start:
                rect_xs.sort()

            # i is length of current rect_xs array
            ans[j] = i - bisect_left(rect_xs, x)
        
        return ans

Explain

本题解采用二分查找的方法，首先对矩形数组按照高度从大到小排序，然后对点数组也按照高度从大到小排序。通过维护一个当前高度下所有矩形的宽度列表（按照宽度排序），对于每个点，找出在其高度要求下所有宽度足够的矩形，利用二分查找确定宽度能包含该点的矩形数量。在遍历点的过程中，随着点的高度的降低，逐渐增加满足条件的矩形宽度到列表中，并更新答案。

时间复杂度: O((m+n) log(m+n))

空间复杂度: O(m + n)

"""
二分查找
时间复杂度: O((m+n) log(m+n))
空间复杂度: O(m + n)
矩形包含点的数量随矩形的l和h是递减的，因此可以使用二分查找
"""
class Solution:
    def countRectangles(self, rectangles: List[List[int]], points: List[List[int]]) -> List[int]:
        m, n = len(rectangles), len(points)
        ans = [0] * n 

        # 1. O(mlogm) 对矩形数组按高度降序排序
        rectangles.sort(key=lambda x: -x[1])

        # 2. O(nlogn) 对点数组按高度降序排序，并保留原索引
        points_indices = sorted(range(n), key=lambda j: -points[j][1])

        # 3. O(n) 遍历排序后的点数组
        i = 0   # 指针遍历排序后的矩形数组
        rect_xs = []    # 存储所有高度大于等于当前点y坐标的矩形的x坐标
        for j in points_indices:
            x, y = points[j]

            # 遍历矩形数组，存储所有高度大于等于y的矩形的x坐标
            start = i 
            while i < m and rectangles[i][1] >= y:
                rect_xs.append(rectangles[i][0])
                i += 1

            # 对rect_xs列表按照x坐标升序排序
            if i > start:
                rect_xs.sort()

            # 使用二分查找确定x坐标大于等于点x坐标的矩形数量
            ans[j] = i - bisect_left(rect_xs, x)
        
        return ans 
"""

Explore

排序的目的是为了有效地处理每个点能被哪些矩形包含的问题。通过按高度降序排列矩形和点，我们可以确保在遍历点时，可以逐步将满足当前点高度条件的矩形宽度添加到考虑的列表中。这样的处理方式保证了每次添加的矩形都是对后续点来说可能有效的，从而避免了对每个点重新计算其上方的矩形，提高了效率。

在原始点数组按高度排序后，我们需要通过索引数组`points_indices`来保持点的原始顺序信息。这样做是因为最终输出的答案需要与输入点的顺序一致。通过使用索引数组，在处理完所有点之后，可以按照原始顺序将结果放置在正确的位置，确保输出的一致性。

这种逐步添加矩形的策略是为了优化算法效率。如果一开始就将所有矩形宽度添加到列表中，我们需要对每个点重新计算符合高度要求的矩形。而按点的高度顺序逐步加入矩形宽度，可以保证一旦矩形被加入列表，就无需再被移除，因为所有后续的点的高度都不会超过当前点。这样可以减少重复的计算和不必要的操作，优化整体的时间复杂度。

`bisect_left`函数在一个已排序的列表中找到第一个不小于给定值x的元素的位置索引。在本题中，这个函数帮助我们快速定位列表`rect_xs`中第一个宽度不小于点x坐标的矩形的位置。由于`rect_xs`是升序的，从这个位置到列表末尾的所有矩形都是宽度大于等于x的，因此这个索引直接帮助我们计算出能包含该点的矩形数量。