Very Simple Java Answer On2


  • 1
    L

    Very Simple Java Answer On2

    public int numberOfBoomerangs(int[][] points) {
            int count = 0;
            for (int i = 0; i < points.length; i++) {
                HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
                for (int j = 0; j < points.length; j++) {
                    int dis = (points[i][0] - points[j][0]) * (points[i][0] - points[j][0]) + (points[i][1] - points[j][1]) * (points[i][1] - points[j][1]);
                    if (!map.containsKey(dis)) {
                        map.put(dis, 0);
                    }
                    count += map.get(dis) * 2;
                    map.put(dis, map.get(dis) + 1);
                }
            }
            return count;
        }

  • 0
    M

    Very nice solution! Better to add some explanations for count += map.get(dis) * 2;:

    When a k-th point with the same distance to the original point is found, we'll add (k-1)*2 pairs of points, i.e. (k, 1), (k, 2), ..., (k, k-1) and (1, k), (2, k), ..., (k-1, k).


  • 1
    M

    This code accesses count so many times, even when map.get(dis) is zero. I made added a small if else to this code and was able to cut running time by almost half. Your code took 412ms when I submitted and with this if else,its down to 192ms.
    New code:

    if (!map.containsKey(dis)) {
    	map.put(dis, 1);
    }else{
    	count += map.get(dis) * 2;
    	map.put(dis, map.get(dis) +1);
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.