NumberOfBoomerangsOPT [source code]

public class NumberOfBoomerangsOPT {
    public int numberOfBoomerangs(int[][] p) {
        int count = 0;
        Map<Integer,Integer> map = new HashMap<>(p.length);
        for (int[] i: p) {
            for (int[] j: p) {
                int dx = i[0] - j[0];
                int dy = i[1] - j[1];
                int d = dx * dx + dy * dy;
                Integer value = map.get(d);
                if (value != null) {
                    count += 2 * value;
                    map.put(d, value + 1);
                } else map.put(d, 1);
            }
            map.clear();
        }
        return count;
    }

    public static void main(String[] args) {
        NumberOfBoomerangsOPT tester = new NumberOfBoomerangsOPT();
        int[][] input1 = {{0,0}, {1,0}, {2,0}};
        System.out.println(tester.numberOfBoomerangs(input1));
    }
}

这个是 discussion 上看来的一个, 但是实际上是 submission 最优解: 112(99.56).

思路感觉跟我自己的代码其实是一样的, 不过有一个重要的优化, 就是算距离的时候, 平方根不取. 这样不仅节省了时间, 而且避免了对 double 的处理, 非常聪明.
事实上这个技巧, 应该长期记忆下来, 因为这个算二维距离的问题以后估计会很常见;
对应的, 还有一个小技巧, 就是不要用Math.pow, 这个的默认的返回值是double, 你还要强行 cast, 没有必要, 不如直接就用乘法.

另外一个技巧是他认为不用判断 i 和 j 相等的情况. 现在想想确实是这样. 不过这个只是提升了代码的简洁度, 对速度是没有多大影响的.

把 map 放在最外层类似于 global 的位置, 通过 clear 来重置, 也比我每一个内循环都单独alloc 一个 map 可能要快一点; 感觉 clear 应该是有自己的优化的.
事实上, 这个速度的优化是非常大的.
这个代码的原作者的核心技巧就是下面的count += 2 * value这个. 其他的地方的优化他并没有做到, 比如这个map clear, 以及 distance 的计算方式.
然后评论下面有个人给他加了这两项优化之后, 速度直接从251到112.

另外一个技巧是他没有用我的思路, 就是1pass 整个过完以后再算排列组合, 而是直接1pass,

count += 2 * value;

这个是精华.

这个想法也是做到非常直接的, 因为每针对一个 i, 我们需要的就是任何一对拥有同样 distance 的 j, 所以每当一个 j 出现并且发现有其他相等 distance 的时候, 直接就等于是+1 pair. 这个思路也可以拓展到其他需要计算排列组合的场合: 排列组合直接用最普通的一个increment buffer就完成了, impressive;

另外顺便提一下其他的discussion 最优解里面用的普通方法:

for(int val : map.values()) {  
    res += val * (val-1);  
}

这个就是算的是排列, 而不是组合, 还是比较直接的. 而且这个避免了对val > 1的判断: 这种情况下直接乘了一个0;

Problem Description

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 i and 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]]
Difficulty:Easy
Category:Algorithms
Acceptance:44.54%
Contributor: alexander54
Companies
google
Related Topics
hash table
Similar Questions
Line Reflection