【算法】1828. 统计一个圆中点的数目(java / c / c++ / python / go / rust)

简介: 给你一个数组 points ,其中 points[i] = [xi, yi] ,表示第 i 个点在二维平面上的坐标。多个点可能会有 相同 的坐标。同时给你一个数组 queries ,其中 queries[j] = [xj, yj, rj] ,表示一个圆心在 (xj, yj) 且半径为 rj 的圆。对于每一个查询 queries[j] ,计算在第 j 个圆 内 点的数目。如果一个点在圆的 边界上 ,我们同样认为它在圆 内 。请你返回一个数组 answer ,其中 answer[j]是第 j 个查询的答案。

1828. 统计一个圆中点的数目:

给你一个数组 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 <= x​​​​​​i, y​​​​​​i <= 500
  • 1 <= queries.length <= 500
  • queries[j].length == 3
  • 0 <= xj, yj <= 500
  • 1 <= rj <= 500
  • 所有的坐标都是整数。

分析

  • 二当家的刚看到题目先是有点懈怠心里,因为几何知识都忘记了,感觉会很复杂。
  • 但是读了题,仔细思考后发现点是否会落在圆内,就是要看点到圆心的距离是否小于等于圆的半径。
  • 假设圆心p1的坐标是(x1,y1),点p2的坐标是(x2,y2),那么点到圆心的距离就是图片.png

  • 由于我们只需要比较距离和半径哪个大,并不需要真的算出距离,所以可以距离不开方,而把半径做平方,因为平方运算要比开方快。

题解

java

class Solution {
    public int[] countPoints(int[][] points, int[][] queries) {
        final int n   = queries.length;
        int[]     ans = new int[n];

        for (int i = 0; i < n; ++i) {
            int x = queries[i][0];
            int y = queries[i][1];
            int r = queries[i][2];
            int r2 = r * r;
            int maxX = x + r;
            int minX = x - r;
            int maxY = y + r;
            int minY = y - r;

            for (int[] p : points) {
                int px = p[0];
                int py = p[1];
                // 加速的判断,是否有意义不好说,对于不符合的点会更快,对于符合的点会更慢,也许就互相抵消了
                if (px < minX || px > maxX
                    || py < minY || py > maxY) {
                    continue;
                }
                // 到圆心距离小于等于半径的点就是满足题目要求的点
                double dis = Math.pow(px - x, 2) + Math.pow(py - y, 2);
                if (dis <= r2) {
                    ans[i]++;
                }
            }
        }

        return ans;
    }
}

c

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* countPoints(int** points, int pointsSize, int* pointsColSize, int** queries, int queriesSize, int* queriesColSize, int* returnSize){
    *returnSize = queriesSize;
    int *ans = malloc(sizeof(int) * queriesSize);

    for (int i = 0; i < queriesSize; ++i) {
        int x = queries[i][0];
        int y = queries[i][1];
        int r = queries[i][2];
        int r2 = r * r;
        int maxX = x + r;
        int minX = x - r;
        int maxY = y + r;
        int minY = y - r;

        int count = 0;

        for (int j = 0; j < pointsSize; ++j) {
            int px = points[j][0];
            int py = points[j][1];
            // 加速的判断,是否有意义不好说,对于不符合的点会更快,对于符合的点会更慢,也许就互相抵消了
            if (px < minX || px > maxX
                || py < minY || py > maxY) {
                continue;
            }
            // 到圆心距离小于等于半径的点就是满足题目要求的点
            double dis = (px - x) * (px - x) + (py - y) * (py - y);
            if (dis <= r2) {
                ++count;
            }
        }

        ans[i] = count;
    }

    return ans;
}

c++

class Solution {
public:
    vector<int> countPoints(vector<vector<int>>& points, vector<vector<int>>& queries) {
        vector<int> ans;

        for (auto &query : queries) {
            int x = query[0];
            int y = query[1];
            int r = query[2];
            int r2 = r * r;
            int maxX = x + r;
            int minX = x - r;
            int maxY = y + r;
            int minY = y - r;

            int count = 0;

            for (auto &point : points) {
                int px = point[0];
                int py = point[1];
                // 加速的判断,是否有意义不好说,对于不符合的点会更快,对于符合的点会更慢,也许就互相抵消了
                if (px < minX || px > maxX
                    || py < minY || py > maxY) {
                    continue;
                }
                // 到圆心距离小于等于半径的点就是满足题目要求的点
                double dis = (px - x) * (px - x) + (py - y) * (py - y);
                if (dis <= r2) {
                    ++count;
                }
            }

            ans.push_back(count);
        }

        return ans;
    }
};

python

class Solution:
    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:
        ans = []

        for x, y, r in queries:
            r2 = r * r
            maxX = x + r
            minX = x - r
            maxY = y + r
            minY = y - r

            count = 0
            for px, py in points:
                # 加速的判断,是否有意义不好说,对于不符合的点会更快,对于符合的点会更慢,也许就互相抵消了
                if (px < minX or px > maxX
                        or py < minY or py > maxY):
                    continue
                # 到圆心距离小于等于半径的点就是满足题目要求的点
                dis = (px - x) ** 2 + (py - y) ** 2
                if dis <= r2:
                    count += 1

            ans.append(count)

        return ans

go

func countPoints(points [][]int, queries [][]int) []int {
    ans := make([]int, len(queries))

    for i, query := range queries {
        x := query[0]
        y := query[1]
        r := query[2]
        r2 := r * r
        maxX := x + r
        minX := x - r
        maxY := y + r
        minY := y - r

        for _, point := range points {
            px := point[0]
            py := point[1]
            // 加速的判断,是否有意义不好说,对于不符合的点会更快,对于符合的点会更慢,也许就互相抵消了
            if px < minX || px > maxX || py < minY || py > maxY {
                continue
            }
            // 到圆心距离小于等于半径的点就是满足题目要求的点
            dis := (px - x) * (px - x) + (py - y) * (py - y)
            if dis <= r2 {
                ans[i]++
            }
        }
    }

    return ans
}

rust

impl Solution {
    pub fn count_points(points: Vec<Vec<i32>>, queries: Vec<Vec<i32>>) -> Vec<i32> {
        queries.iter().map(|query| {
            let (x, y, r) = (query[0], query[1], query[2]);
            let r2 = r * r;
            let max_x = x + r;
            let min_x = x - r;
            let max_y = y + r;
            let min_y = y - r;

            points.iter().map(|point| {
                let (px, py) = (point[0], point[1]);
                if px >= min_x && px <= max_x
                    && py >= min_y && py <= max_y {
                    // 到圆心距离小于等于半径的点就是满足题目要求的点
                    let dis = (px - x) * (px - x) + (py - y) * (py - y);
                    if dis <= r2 {
                        return 1;
                    }
                }
                0
            }).sum()
        }).collect()
    }
}

原题传送门


非常感谢你阅读本文~
放弃不难,但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子:https://developer.aliyun.com/profile/sqd6avc7qgj7y 博客原创~

相关文章
|
2月前
|
算法 安全 Go
Go 语言中实现 RSA 加解密、签名验证算法
随着互联网的发展,安全需求日益增长。非对称加密算法RSA成为密码学中的重要代表。本文介绍如何使用Go语言和[forgoer/openssl](https://github.com/forgoer/openssl)库简化RSA加解密操作,包括秘钥生成、加解密及签名验证。该库还支持AES、DES等常用算法,安装简便,代码示例清晰易懂。
63 12
|
6月前
|
算法框架/工具 C++ Python
根据相机旋转矩阵求解三个轴的旋转角/欧拉角/姿态角 或 旋转矩阵与欧拉角(Euler Angles)之间的相互转换,以及python和C++代码实现
根据相机旋转矩阵求解三个轴的旋转角/欧拉角/姿态角 或 旋转矩阵与欧拉角(Euler Angles)之间的相互转换,以及python和C++代码实现
475 0
|
3月前
|
算法 关系型数据库 MySQL
分布式唯一ID生成:深入理解Snowflake算法在Go中的实现
在分布式系统中,确保每个节点生成的 ID 唯一且高效至关重要。Snowflake 算法由 Twitter 开发,通过 64 位 long 型数字生成全局唯一 ID,包括 1 位标识位、41 位时间戳、10 位机器 ID 和 12 位序列号。该算法具备全局唯一性、递增性、高可用性和高性能,适用于高并发场景,如电商促销时的大量订单生成。本文介绍了使用 Go 语言的 `bwmarrin/snowflake` 和 `sony/sonyflake` 库实现 Snowflake 算法的方法。
104 1
分布式唯一ID生成:深入理解Snowflake算法在Go中的实现
|
4月前
|
数据可视化 数据挖掘 Python
Seaborn 库创建吸引人的统计图表
【10月更文挑战第11天】本文介绍了如何使用 Seaborn 库创建多种统计图表,包括散点图、箱线图、直方图、线性回归图、热力图等。通过具体示例和代码,展示了 Seaborn 在数据可视化中的强大功能和灵活性,帮助读者更好地理解和应用这一工具。
55 3
|
4月前
|
C++ Python
探索Python与C/C++混合编程的艺术
探索Python与C/C++混合编程的艺术
79 1
|
4月前
|
JSON 数据格式 Python
Python实用记录(十四):python统计某个单词在TXT/JSON文件中出现的次数
这篇文章介绍了一个Python脚本,用于统计TXT或JSON文件中特定单词的出现次数。它包含两个函数,分别处理文本和JSON文件,并通过命令行参数接收文件路径、目标单词和文件格式。文章还提供了代码逻辑的解释和示例用法。
67 0
Python实用记录(十四):python统计某个单词在TXT/JSON文件中出现的次数
|
4月前
|
算法 安全 Go
RSA加密算法详解与Python和Go实现
RSA加密算法详解与Python和Go实现
309 1
|
4月前
|
数据可视化 Serverless Python
Python小事例—质地不均匀的硬币的概率统计
Python小事例—质地不均匀的硬币的概率统计
80 0
|
4月前
|
安全 测试技术 Go
Python 和 Go 实现 AES 加密算法的技术详解
Python 和 Go 实现 AES 加密算法的技术详解
189 0
WK
|
5月前
|
机器学习/深度学习 Java 程序员
为什么Python比C++慢很多?
Python相较于C++较慢主要体现在:动态类型系统导致运行时需解析类型,增加开销;作为解释型语言,逐行转换字节码的过程延长了执行时间;自动内存管理和垃圾回收机制虽简化操作但也带来了额外负担;全局解释器锁(GIL)限制了多线程性能;尽管Python库方便灵活,但在性能上往往不及C++底层库。然而,Python在某些领域如数据分析、机器学习中,凭借其高级别抽象和简洁语法仍表现出色。选语言需依据具体应用场景和需求综合考量。
WK
129 1