LeetCode 0447.回旋镖的数量:哈希表
【LetMeFly】447.回旋镖的数量:哈希表
力扣题目链接:https://leetcode.cn/problems/number-of-boomerangs/
给定平面上?n
对 互不相同 的点?points
,其中 points[i] = [xi, yi]
。回旋镖 是由点?(i, j, k)
表示的元组 ,其中?i
?和?j
?之间的距离和?i
?和?k
?之间的欧式距离相等(需要考虑元组的顺序)。
返回平面上所有回旋镖的数量。
?示例 1:
输入:points = [[0,0],[1,0],[2,0]] 输出:2 解释:两个回旋镖为 [[1,0],[0,0],[2,0]] 和 [[1,0],[2,0],[0,0]]
示例 2:
输入:points = [[1,1],[2,2],[3,3]] 输出:2
示例 3:
输入:points = [[1,1]] 输出:0
?
提示:
n ==?points.length
1 <= n <= 500
points[i].length == 2
-104 <= xi, yi <= 104
- 所有点都 互不相同
方法一:哈希表
第一重循环枚举每个 j j j点。对于points[j],使用一个哈希表,记录所有的点到j点的距离的出现次数。然后遍历哈希表,假设某距离出现了cnt次,那么就将 c n t × ( c n t ? 1 ) cnt\times(cnt-1) cnt×(cnt?1)累加到答案中。
- 时间复杂度 O ( l e n ( p o i n t s ) 2 ) O(len(points)^2) O(len(points)2)
- 空间复杂度 O ( l e n ( p o i n t s ) ) O(len(points)) O(len(points))
AC代码
C++
class Solution {
public:
int numberOfBoomerangs(vector<vector<int>>& points) {
int ans = 0;
for (vector<int>& p : points) {
unordered_map<int, int> ma;
for (vector<int>& q : points) {
ma[(p[0] - q[0]) * (p[0] - q[0]) + (p[1] - q[1]) * (p[1] - q[1])]++;
}
for (auto [_, cnt] : ma) {
ans += cnt * (cnt - 1);
}
}
return ans;
}
};
Python
# from typing import List
# from collections import defaultdict
class Solution:
def numberOfBoomerangs(self, points: List[List[int]]) -> int:
ans = 0
for p in points:
ma = defaultdict(int)
for q in points:
ma[(p[0] - q[0]) * (p[0] - q[0]) + (p[1] - q[1]) * (p[1] - q[1])] += 1
for _, cnt in ma.items():
ans += cnt * (cnt - 1)
return ans
同步发文于CSDN,原创不易,转载经作者同意后请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/135464460
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!