[leetcode] Number of Boomerangs

Given n points in the plane that are all pairwise distinct, a "boomerang" is a tuple of points (i, j, k) such that the distance between iand j equals the distance between i and k (the order of the tuple matters).

Find the number of boomerangs. You may assume that n will be at most 500 and coordinates of points are all in the range [-10000, 10000] (inclusive).

Example:

Input:
[[0,0],[1,0],[2,0]]

Output:
2

Explanation:
The two boomerangs are [[1,0],[0,0],[2,0]] and [[1,0],[2,0],[0,0]]

---

 分析：题目意思理解起来并不是很难，二维数组的每一行代表平面上的一个点，任意一个点到其他两个点距离相同时，视为一个解。这里要注意的是其他两个点也是分先后顺序的，也就是可以看成是一个排列问题。有了这个作为基础，首先想到的就是计算所有点之间的距离，并且用一个二维矩阵保存下来。然后去遍历这个二维矩阵的每一行，假设一行有m个相同距离为1的点，那么就是A(m,2)。

        有了上面的分析，首先想到找排列公式，在网上找了一个递归版本的求排列和组合的代码，用java描述如下：

    /**
     * 计算阶乘数，即n! = n * (n-1) * ... * 2 * 1 
     * @param n
     * @return
     */
    private static long factorial(int n) {
        long sum = 1;
        while( n > 0 ) {
            sum = sum * n--;
        }
        return sum;
    }
    /**
     * 排列计算公式A<sup>m</sup><sub>n</sub> = n!/(n - m)!
     * @param m
     * @param n
     * @return
     */
    public static long arrangement(int m, int n) {
        return m <= n ? factorial(n) / factorial(n - m) : 0;
    }
    /**
     * 组合计算公式C<sup>m</sup><sub>n</sub> = n! / (m! * (n - m)!)
     * @param m
     * @param n
     * @return
     */
    public static long combination(int m, int n) {
        return m <= n ? factorial(n) / (factorial(m) * factorial((n - m))) : 0;
    }

      那么本题的代码如下：

    int res = 0;
    public int numberOfBoomerangs(int[][] points) {
        int n = points.length;
        double[][] distance = new double[n][n];
        for ( int i = 0 ; i < n ; i ++ ){
            for ( int j = 0 ; j < n ; j ++ ){
                distance[i][j] = Math.sqrt((points[j][0]-points[i][0])*(points[j][0]-points[i][0])+(points[j][1]-points[i][1])*(points[j][1]-points[i][1]));
            }
        }
        Map<Double,Integer> map = new HashMap<>();
        for ( int i = 0 ; i < n ; i ++ ){
            map.clear();
            for ( int j = 0 ; j < n ; j ++ ){
                map.put(distance[i][j],map.getOrDefault(distance[i][j],0)+1);
            }
            for ( int value : map.values() ){
                if ( value >= 2 ) calcnum(value);
            }
        }
        return res;
    }
    private void calcnum(int value) {
        res += factorial(value) / factorial(value-2);
    }
    private static long factorial(int n) {
        long sum = 1;
        while( n > 0 ) {
            sum = sum * n--;
        }
        return sum;
    }

      最后运行时间117ms，超过94.7%的人。

---

      但是，还是有很大的优化空间，首先在计算距离矩阵的时候，没必要先全部保存下来然后再遍历，可以一边计算，一边用Map记录；而且对于A(m,2)，计算下来的结果就是m*(m-1)，所以也没必要再用递归来做了；因为只要找距离相同的点的个数，也不需用求根号了；这样优化下来，第二版代码如下：

class Solution {
    public int numberOfBoomerangs(int[][] points) {
        int res = 0;
        Map<Double,Integer> map = new HashMap<>();
        int n = points.length;
        for ( int i = 0 ; i < n ; i ++ ){
            for ( int j = 0 ; j < n ; j ++ ){
                double d = (points[j][0]-points[i][0])*(points[j][0]-points[i][0])+(points[j][1]-points[i][1])*(points[j][1]-points[i][1]);
                map.put(d,map.getOrDefault(d,0)+1);
            }
            for ( int value : map.values() ){
                if ( value >= 2 ) res += value*(value-1);
            }
            map.clear();
        }
        return res;
    }
}

      运行时间97ms，超过99%的人。