2024.1.8力扣每日一题——回旋镖的数量

题目来源

力扣每日一题；题序：447

我的题解

方法一 双层哈希表

构造如下的哈希表：{节点i：{距离1：数量，…距离n：数量}}
相当于求每个节点与其他 节点的欧式距离，并统计相同距离的数量，最后计算回旋镖的数量只需要看相同欧氏距离的数量超过1个的，由于可以换顺序，因此相当于在k个满足的节点之间选两个，并且有两种顺序，所以每一组的贡献为：$\frac{k(k-1)}{2}\times 2$

时间复杂度：O($n^2$)。n是节点的数量。
空间复杂度：O($n^2$)。

public int numberOfBoomerangs(int[][] points) {
    int n=points.length;
    Map<Integer,Map<Double,Integer>> count=new HashMap<>();
    for(int i=0;i<n;i++){
        Map<Double,Integer> t=new HashMap<>();
        for(int j=0;j<n;j++){
            if(i==j)
                continue;
            double dis=distance(points[i][0],points[i][1],points[j][0],points[j][1]);
            t.put(dis,t.getOrDefault(dis,0)+1);
        }
        count.put(i,t);
    }
    // System.out.println(count);
    int res=0;
    for(int key:count.keySet()){
        Map<Double,Integer> t=count.get(key);
        for(Double dis:t.keySet()){
            int m=t.get(dis);
            if(m>=2){
                res+=m*(m-1);
            }
        }
    }
    return res;
}   
public double distance(int x1,int y1,int x2,int y2){
    return Math.sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

方法二 哈希表优化版

首先外围的哈希表实际并没有什么用，我们可以在每次构建完成哈希表之后就计算以当前节点尾回旋镖中间节点的的回旋镖数量，并不需要使用两层哈希表保留结果，然后最后再同一计算。

时间复杂度：O($n^2$)
空间复杂度：O(n)

public int numberOfBoomerangs(int[][] points) {
   int n=points.length;
    int res=0;
    for(int i=0;i<n;i++){
        Map<Integer,Integer> t=new HashMap<>();
        for(int j=0;j<n;j++){
            if(i==j)
                continue;
            int dis=distance(points[i][0],points[i][1],points[j][0],points[j][1]);
            t.put(dis,t.getOrDefault(dis,0)+1);
        }
        for(Integer dis:t.keySet()){
            int m=t.get(dis);
            res+=m*(m-1);
        }
    }
    return res;
}   
public int distance(int x1,int y1,int x2,int y2){
    return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈