6043. 统计包含每个点的矩形数目二分查找

vlambda
2022-04-30

6043. 统计包含每个点的矩形数目二分查找

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

给你一个二维整数数组 `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：

6043. 统计包含每个点的矩形数目二分查找

输入：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 互不相同。

来源：力扣（LeetCode）

链接：https://leetcode.cn/problems/count-number-of-rectangles-containing-each-point

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方法：二分查找

列只有100，可枚举所有列，然后二分查找，具体如下

排序并建立列->行集合的映射
遍历所有点

查找 y 到 100（列最大值）超过指定的x的数目【在y比预定值大的情况下，找有多少个x比预定值大，就是多少个正方形包括该点】
累加计入当前位置答案

class Solution {
    public int[] countRectangles(int[][] rectangles, int[][] points) {
        Arrays.sort(rectangles, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1]==o2[1]?o2[0]-o1[0]:o1[1]-o2[1];
            }
        });
        Map<Integer,List<Integer>> map = new HashMap<>();
        for(int[] rectangle:rectangles){
            map.putIfAbsent(rectangle[1],new ArrayList<>());
            map.get(rectangle[1]).add(rectangle[0]);
        }

        int n = points.length;
        int[] ans = new int[n];
        for(int i = 0; i < n; i++){
            int[] point = points[i];
            int cnt = 0;
            for(int y = point[1]; y <= 100; y++){
                cnt += getCnt(map.get(y),point[0]);
            }
            ans[i] = cnt;
        }
        return ans;
    }

    private int getCnt(List<Integer> list, Integer x){
        if(list == null) return 0;
        int left =-1;
        int right = list.size()-1;
        while(left<right){
            int mid = (right-left+1)/2 + left;
            if(list.get(mid)>=x){
                left = mid;
            }else{
                right = mid-1;
            }
        }

        return left+1;
    }
}

时间复杂度：O(mlogm+O(n*100logt)),其中m为 rectangles 的长度， n 为 points 的长度, t为当前 y 对应的列表长度
空间复杂度：O(m),其中m为 rectangles 的长度

vlambda博客
学习文章列表