LeetCode 0447.回旋镖的数量:哈希表

2024-01-08 20:36:33

【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

文章来源:https://blog.csdn.net/Tisfy/article/details/135464460
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。