Medium

题目描述

给你一个数组 points，其中 points[i] = [xi, yi] 是第 i 个点在二维平面上的坐标。多个点可能具有相同的坐标。

同时给你一个数组 queries，其中 queries[j] = [xj, yj, rj] 描述一个圆心在 (xj, yj) 且半径为 rj 的圆。

对于每个查询 queries[j]，计算在第 j 个圆 内 点的数目。如果一个点在圆的 边界上，我们同样认为它在圆 内。

返回数组 answer，其中 answer[j] 是第 j 个查询的答案。

示例 1：

输入：points = [[1,3],[3,3],[5,3],[2,2]], queries = [[2,3,1],[4,3,1],[1,1,2]]
输出：[3,2,2]
解释：所示圆和点如上图。
queries[0] 是绿色的圆，queries[1] 是红色的圆，queries[2] 是蓝色的圆。

示例 2：

输入：points = [[1,1],[2,2],[3,3],[4,4],[5,5]], queries = [[1,2,2],[2,2,2],[4,3,2],[4,3,3]]
输出：[2,3,2,4]
解释：所示圆和点如上图。
queries[0] 是绿色的，queries[1] 是红色的，queries[2] 是蓝色的，queries[3] 是紫色的。

提示：

  • 1 <= points.length <= 500
  • points[i].length == 2
  • 0 <= xi, yi <= 500
  • 1 <= queries.length <= 500
  • queries[j].length == 3
  • 0 <= xj, yj <= 500
  • 1 <= rj <= 500
  • 所有坐标都是整数

进阶： 你可以设计一个在每次查询时都比 O(n) 更快的算法吗？

解题思路

这道题要求我们判断有多少个点在给定的圆内。解决方案的核心是利用欧几里得距离公式。

基本思路： 对于一个点 (px, py) 和圆心 (cx, cy)，如果点到圆心的距离小于等于半径 r，那么这个点就在圆内（包括边界）。

距离公式为：distance = sqrt((px-cx)² + (py-cy)²) 判断条件：distance <= r

为了避免浮点数运算和开方操作，我们可以对不等式两边同时平方： (px-cx)² + (py-cy)² <= r²

算法步骤：

  1. 遍历每个查询圆
  2. 对于每个圆，遍历所有点
  3. 计算点到圆心距离的平方
  4. 如果距离平方小于等于半径平方，计数器加1
  5. 将每个查询的结果存入答案数组

复杂度优化思考： 题目提到进阶要求，可以考虑使用空间数据结构如四叉树、K-D树等来优化查询，但在当前数据规模下（最多500个点和500次查询），暴力解法已经足够高效。

代码实现

class Solution {
public:
    vector<int> countPoints(vector<vector<int>>& points, vector<vector<int>>& queries) {
        vector<int> answer;
        
        for (const auto& query : queries) {
            int cx = query[0], cy = query[1], r = query[2];
            int count = 0;
            
            for (const auto& point : points) {
                int px = point[0], py = point[1];
                int distanceSquared = (px - cx) * (px - cx) + (py - cy) * (py - cy);
                if (distanceSquared <= r * r) {
                    count++;
                }
            }
            
            answer.push_back(count);
        }
        
        return answer;
    }
};

class Solution:
    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:
        answer = []
        
        for cx, cy, r in queries:
            count = 0
            for px, py in points:
                distance_squared = (px - cx) ** 2 + (py - cy) ** 2
                if distance_squared <= r * r:
                    count += 1
            answer.append(count)
        
        return answer

public class Solution {
    public int[] CountPoints(int[][] points, int[][] queries) {
        int[] answer = new int[queries.Length];
        
        for (int i = 0; i < queries.Length; i++) {
            int cx = queries[i][0], cy = queries[i][1], r = queries[i][2];
            int count = 0;
            
            foreach (var point in points) {
                int px = point[0], py = point[1];
                int distanceSquared = (px - cx) * (px - cx) + (py - cy) * (py - cy);
                if (distanceSquared <= r * r) {
                    count++;
                }
            }
            
            answer[i] = count;
        }
        
        return answer;
    }
}

var countPoints = function(points, queries) {
    const answer = [];
    
    for (const [cx, cy, r] of queries) {
        let count = 0;
        for (const [px, py] of points) {
            const distanceSquared = (px - cx) * (px - cx) + (py - cy) * (py - cy);
            if (distanceSquared <= r * r) {
                count++;
            }
        }
        answer.push(count);
    }
    
    return answer;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(m × n)其中 m 是查询次数，n 是点的数量。需要对每个查询遍历所有点
空间复杂度O(1)除了存储答案的数组外，只使用了常数额外空间

相关题目