Leetcode 447：Number of Boomerangs

You are given n points in the plane that are all distinct, where points[i] = [xi, yi]. A boomerang is a tuple of points (i, j, k) such that the distance between i and j equals the distance between i and k (the order of the tuple matters).

Return the number of boomerangs.

说人话：

给定平面上 n 对互不相同的点 points ，其中 points[i] = [xi, yi] 。回旋镖是由点 (i, j, k) 表示的元组 ，其中 i 和 j 之间的距离和 i 和 k 之间的距离相等（需要考虑元组的顺序）。

返回平面上所有回旋镖的数量。

几个要点：

• 点是不同的点
• 点 i 是枢纽
• 返回的是回旋镖的数量，不是具体的回旋镖
• n == points.length
• 1 <= n <= 500：说明我们可以接受 O(n²) 级别的算法
• points[i].length == 2
• -10⁴ <= xi, yi <= 10⁴，所以算距离的时候不会出现溢出

示例：

[法1] 暴力法

思路

• 遍历所有点的情况
• 三层循环，找到符合条件的元组
• 记录元组个数

代码

class Solution {
    public int numberOfBoomerangs(int[][] points) {

        int result = 0;

        //三层遍历
        for(int a=0;a<points.length;a++){
            for(int b=0;b<points.length;b++){
                for(int c=0;c<points.length;c++){
                    //A.B.C为三个不同的点
                    if( a!=b && a!=c && b!=c){
                        //A.B的距离
                        int distanceAB = 
                          (points[a][0]-points[b][0])*(points[a][0]-points[b][0])+ 
                          (points[a][1]-points[b][1])*(points[a][1]-points[b][1]);
                        //A.C的距离
                        int distanceAC = 
                          (points[a][0]-points[c][0])*(points[a][0]-points[c][0])+ 
                          (points[a][1]-points[c][1])*(points[a][1]-points[c][1]);
                        //距离相等则累加
                        if( distanceAB == distanceAC){
                            result++;
                        }
                    }

                }
            }
        }
        return result;
    }
}

提交结果

代码分析

• 时间复杂度：O(n³)
• 空间复杂度：O(1)

改进思路

因为 N 的级别为 500，所以我们可以接受 n² 的复杂度， n³ 就太大了。我们需要想办法将时间复杂度降为 O(n²) 甚至更低。

[法2] 查找表灵活选择键值

思路

我们可以发现题目中 点 i 其实是一个枢纽，那么我们就可以对于每个 点 i，遍历其他剩余点到 点 i 的距离，然后看看相同距离的点有多少个，对这些相同距离的点进行排列组合 A_n²，就可以了。

整体思路如下：

• 遍历所有点 i
• 对每一个点 i 记录其他所有点与点 i 的距离，并记录相同距离的点的个数
• 对这些相同距离的点进行排列组合 A_n²
• 累计所有的点 i 得到回旋镖的个数

代码

class Solution {
    public int numberOfBoomerangs(int[][] points) {

        int result = 0;

        //遍历每一个点 i
        for(int i=0;i<points.length;i++){

            Map<Integer,Integer> map = new HashMap<>();

            //以 i 作为枢纽
            for(int j=0;j<points.length;j++){
                //记录其他点到点 i 的距离
                if( i!=j ){
                    //距离的平方
                    int distance = 
                    (points[i][0]-points[j][0])*(points[i][0]-points[j][0]) + 
                    (points[i][1]-points[j][1])*(points[i][1]-points[j][1]);

                    //统计相同记录的点的个数
                    Integer count = map.get(distance);
                    if(count !=null && count>0){
                        count++;
                        map.put(distance,count);
                    }else{
                        map.put(distance,1);
                    }
                }
            }

            //对这些相同距离的点进行排列组合
            Set<Integer> keys = map.keySet();
            for(Integer key: keys){
                Integer count = map.get(key);
                if(count != null && count >= 2){
                    result += (count)*(count-1);
                }
            }
        }
        return result;
    }
}

提交结果

代码分析

• 时间复杂度：O(n²)。
• 空间复杂度：因为对于每一个点 i 操作完成后都会释放 map，然后再申请，所以自始至终都只需要 O(n) 的辅助空间。

陷阱

本题中保证点的坐标在 [-10000,10000] 的范围内，所以算距离的时候不会发生整数溢出。如果没有这个条件的话，最好算距离的时候转为 long 或者 decimal 来进行计算，避免整数溢出。