LeetCode 1828. Count the number of points in a circle

1828. Count the number of points in a circle

Give you an array points , among points[i] = [xi, yi] , It means the first one i The coordinates of a point on a two-dimensional plane . Multiple points may have identical Coordinates of .

I'll give you an array at the same time queries , among queries[j] = [xj, yj, rj] , The center of a circle (xj, yj) And the radius is rj The circle of .

For every query queries[j] , The calculation is in j Circle Inside Number of points . If a point is on the edge of a circle On the border , We also think it's round Inside .

Please return an array answer , among answer[j] It's No j The answer to a query .

Example 1：

 Input ：points = [[1,3],[3,3],[5,3],[2,2]], queries = [[2,3,1],[4,3,1],[1,1,2]]
 Output ：[3,2,2]
 explain ： All the points and circles are shown in the figure above .
queries[0]  It's a green circle ,queries[1]  It's a red circle ,queries[2]  It's a blue circle .

Example 2：

 Input ：points = [[1,1],[2,2],[3,3],[4,4],[5,5]], queries = [[1,2,2],[2,2,2],[4,3,2],[4,3,3]]
 Output ：[2,3,2,4]
 explain ： All the points and circles are shown in the figure above .
queries[0]  It's a green circle ,queries[1]  It's a red circle ,queries[2]  It's a blue circle ,queries[3]  It's a purple circle .

Tips ：

• 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
• All coordinates are integers .

Two 、 Method 1

simulation

class Solution {
    
    public int[] countPoints(int[][] points, int[][] queries) {
    

        int[] answer = new int[queries.length];

        for(int i=0;i<queries.length;i++){
    
            int[] cur = queries[i];
            int x = cur[0];
            int y = cur[1];
            int r = cur[2];

            int sum=0;
            for(int[] p:points){
    
                int a = p[0] - x;
                int b = p[1]- y;
                if(a*a+b*b<=r*r) sum++;
            }

            answer[i] = sum;

        }

        return answer;
    }
}

Complexity analysis

• Time complexity ：O(n).

• Spatial complexity ：O(1).