【Day 20】回旋镖的数量

题目描述

给定平面上 n 对不同的点，“回旋镖” 是由点表示的元组 (i, j, k) ，其中 i 和 j 之间的距离和 i 和 k 之间的距离相等（需要考虑元组的顺序）。
 
找到所有回旋镖的数量。你可以假设 n 最大为 500，所有点的坐标在闭区间 [-10000, 10000] 中。
 
示例:
 
输入:
[[0,0],[1,0],[2,0]]
 
输出:
2
 
解释:
两个回旋镖为 [[1,0],[0,0],[2,0]] 和 [[1,0],[2,0],[0,0]]
 
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-boomerangs
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我的回答

解法一

时间复杂度 O(n*n)

空间复杂度 O(n)

var numberOfBoomerangs = function (points) {
    let res = 0
    for (let i = 0; i < points.length; i++) {
        let map = {}
        for (let j = 0; j < points.length; j++) {
            let x = points[j][0] - points[i][0]
            let y = points[j][1] - points[i][1]
            let dist = Math.sqrt(Math.pow(x, 2) + Math.pow(y, 2));
            map[dist] = map[dist] ? map[dist] + 1 : 1
        }
        for (let i in map) {
            res += map[i] * (map[i] - 1)
        }
    }
    return res
};

参考回答

#447 回旋镖的数量

多读两遍题，大概就明白了题意：就是找出所有符合三个点 x,y,z，并且 dis(x,y)=dis(x,z)这种点的个数。首先要明确两点间距离怎么计算，忘了是小学还是初中的知识了：

$$x=(x1,x2)$$ $$y=(y1,y2)$$ $$dis(x,y)=\sqrt{(x1-y1{)}^2+(x2-y2{)}^2}$$

由于求的是算数平方根，所以我们算距离的时候也没必要开根号了

我们可以很容易地想到暴力解法，也就是来个三重循环

public int numberOfBoomerangs(int[][] points) {
 
 if (points == null || points.length <= 2)
     return 0;
 
 int res = 0;
 
 for (int i = 0; i < points.length; i++) {
 
     for (int j = 0; j < points.length; j++) {
 
         if (i == j)
             continue;
 
         for (int k = 0; k < points.length; k++) {
 
             if (k == i || k == j)
                 continue;
 
             if (getDistance(points[i], points[j]) == getDistance(points[i], points[k]))
                 res++;
         }
     }
 }
 
 return res;
}
 
private int getDistance(int[] x, int[] y) {
 
 int x1 = y[0] - x[0];
 int y1 = y[1] - x[1];
 
 return x1 * x1 + y1 * y1;
}

这就相当于把题目翻译了一遍，但是提交就会发现 TLE 了，也不难发现时间复杂度是$O(N^3)$，

也就是我们需要优化代码了。。。首先题目说 n 个点不同且答案考虑元组顺序，那么我们最外层循环是跑不掉了，因为需要固定每一个点。

里面两层循环可不可以优化一下呢，其实不难想，当我们固定其中一个点 A 的时候，并且想算距离为 3 的点的个数，那么我们就找出所有和点 A 距离为 3 的点，然后来一个简单的排列组合嘛！比如找到了 n 个距离为 3 的点，那么我们选择第二个点有 n 种方案，选择第三个点有(n - 1)个方案，那么固定点 A 且距离为 3 的所有可能就是 n*(n-1)，这是说距离为 3，还有许多其他距离呢，这不就又回到了我们统计元素频率的问题上了嘛，当然哈希表用起来！上代码：

public int numberOfBoomerangs(int[][] points) {
 
 if (points == null || points.length <= 2)
     return 0;
 
 int res = 0;
 Map<Integer, Integer> equalCount = new HashMap<>();
 
 for (int i = 0; i < points.length; ++i) {
 
     for (int j = 0; j < points.length; ++j) {
 
         int dinstance = getDistance(points[i], points[j]);
         equalCount.put(dinstance, equalCount.getOrDefault(dinstance, 0) + 1);
     }
 
     for (int count : equalCount.values())
         res += count * (count - 1);
     equalCount.clear();
 }
 
 return res;
}
 
private int getDistance(int[] x, int[] y) {
 
 int x1 = y[0] - x[0];
 int y1 = y[1] - x[1];
 
 return x1 * x1 + y1 * y1;
}

这样时间复杂度就被优化为$O(N^2\ast max(differen{t}_{d}istanc{e}_{c}ount))$

ps: 希望大家自己动手实现输入输出格式，输入格式可以如下：

第一行代表n个点，后面有n行数据 用空格分割元素
5
1 2
0 1
0 2
3 2
2 3