NumberOfBoomerangs [source code]

public class NumberOfBoomerangs {
    public int numberOfBoomerangs(int[][] points) {
        int res = 0;
        int n = points.length; 
        for (int i = 0; i < n; i++) {
            Map<Integer, Integer> dict = new HashMap<>();
            for (int j = 0; j < n; j++) {
                if (j == i) continue;
                Integer distance = distance(points[i], points[j]);
                Integer count = dict.get(distance);
                if (count == null) {
                    dict.put(distance, 1);
                } else {
                    dict.put(distance, count + 1);
                }
            }

            for (Map.Entry e : dict.entrySet()) {
                int count = (int) e.getValue();
                if (count > 1) res += chooseCount(count, 2) * 2;
            }
        }
        return res;
    }

    public int distance(int[] p1, int[] p2) {
        int dx = p1[0] - p2[0];
        int dy = p1[1] - p2[1];
        return dx * dx + dy * dy;
    }

    public int chooseCount(int n, int k) {
        return factorial(n) / (factorial(n - k) * factorial(k));
    }

    public int factorial(int num) {
        int res = 1;
        for (int i = 1; i <= num; i++) res *= i;
        return res;
    }

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

这个算法总体来说是对的, 不过太慢了, 就算不算 hashmap 带来的减速效果, 本身就已经是 quadratic 了. 所以优化的效果要么就是做到subquadratic, 要么就是用其他的方式来实现 hashtable.

不过还是很多需要学习的地方:

System.out.println(tester.distance(new int[]{1,2}, new int[]{3,4}));

这里, 当array literal直接作为 argument, 或者直接 inline 使用的时候, 一般要 new 一下, 直接写好像很容易报错; 像我们平时:

int[] ar = {1,2};

这样的, 估计只是一个syntactical sugar.

这个写法是一个很危险的写法, 看起来没有问题, 实际上这里忘记了++的优先级顺序;

dict.put(distance, count++);

这里这个错误我不是第一次犯了, 两个 header 写成了这样:

for (int i = 0; i < n; i++)   
    for (int j = 0; j < n && j != i; j++)

这个直接导致里面的循环在某些 i 的取值的情况下根本就不执行了. 看起来用&&来把 if 放到 header 里面很 slick, 其实如果放到 body 里面也就是多一个 continue 的事情. 这样写很容易出错, 这里已经不是第一次了. header 的第二项, 不是一个 filter, 而是一个termination condition.

看 discussion 之后学到一个举例计算上的优化, 使用之后, AC 了, 速度是: 266(24). 不算特别好, 不过好歹 AC 了;

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