【每日一题Day97】LC1828统计一个圆中点的数目 | 模拟
admin
2024-05-16 11:34:42
0次

统计一个圆中点的数目【LC1828】

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

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

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

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

看到这题的时候我脑子里闪过了许多想法：离线查询，二维累加和数组……但是都不行，还是暴力吧

  • 思路：双重循环计算每个点到圆点的距离，如果小于等于半径，则证明在圆内

  • 实现

    class Solution {public int[] countPoints(int[][] points, int[][] queries) {int n = queries.length;int[] ans = new int[n];for (int i = 0; i < n; i++){for (int[] p : points){double dis = Math.pow(p[0] - queries[i][0], 2) + Math.pow(p[1] - queries[i][1], 2);if (dis <= Math.pow(queries[i][2], 2)){ans[i]++;}}}return ans;}
}
    • 复杂度
      • 时间复杂度：O(n∗m)O(n*m)O(n∗m)，n和m分别为点的数量和圆的数量
      • 空间复杂度：O(1)O(1)O(1)
词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：《Rust权威指南》读书笔记9 - 泛型、特性、生命周期

下一篇：Intellij IDEA导入jar包的方法

相关内容

热门资讯

国庆假期中外旅游“双向奔赴” 　　新华社北京10月7日电　2026年国庆假期，中国游客走出国门，欣赏远方的风景；而外国游客从世界各...
长假尾声 游兴不减 10月7日，游客在浙江杭州西湖风景区游览。 新华社记者 徐昱 摄　　国庆长假进入尾声，人们赏美景，品...
这座晋南古镇，在保护与烟火中复... 　　新华社太原10月7日电（记者邓浩然）“这有什么看头？”自幼在山西襄汾汾城长大的郑彦文，曾经面对汹...
瞰中国｜湖北丹江口：夜游汉江乐... 国庆假期，湖北省丹江口市依托汉江两岸山水资源，推出系列夜游项目，多处景点联动开放，吸引四方游客前来打...
“外来客”首超八成，看，山东沂... 齐鲁晚报·齐鲁壹点 通讯员 郑树平今年国庆假期，山东红嫂家乡旅游区红色旅游火爆出圈。黄金周后盘点，大...
记者手记：千年盐田 古韵新生 　　新华社天津10月7日电（记者赵子硕）“呜——”汽笛轻鸣，这是天津长芦海盐文化旅游区今年国庆假期新...
成都崇州国庆期间设置“红黑榜”... 四川在线记者熊晓雨国庆假期，元通古镇游人如织，几块新设立的“红黑榜”引人注目。游客雷睿鑫感慨道：“红...
乐享假日时光，国庆期间超2.1... 这个国庆假期，各地公园举办丰富多彩的文化活动，超过2.1亿人次在公园乐享假日时光。白天赏秋，晚上夜游...
国庆出游“含城量”提升，美团：... “十一”假期进入尾声，不少游客踏上返程。10月7日，根据《美团2026国庆消费洞察报告》（以下简称《...
位居多个旅游榜单热门目的地首位... 2026国庆假期落下帷幕，来自多个平台的数据显示，今年中秋国庆出行需求整体增长，不但入境游订单同比实...