Using HashMap in Java


  • 0
    I

    Each point needs to calculate the distances between itself and all the other points to find out the number of boomerangs.
    Using a map to record the distance and the number of the distance occurs.
    For example: there are 4 points in the plane -- [[0,0],[1,0],[-1,0],[0,1]]

    Take [0,0] as the main point:

    • After [1,0] is in the calculation; then map has key-value pair as [1,1], key is the distance and the value is the number of occurrence of this distance.
    • Next, [-1,0] enters into the calculation, there has already been a distance -- 1, so the number of boomerangs is 2 (because the order matters) -- map has key-value pair as [1,2].
    • When [0,1] enters into the calculation, there are already 2 values is 1, so the boomerangs should be 4
      • [0,0],[1,0],[0,1]; [0,0],[-1,0],[0,1]; [0,0],[0,1],[1,0]; [0,0],[0,1],[-1,0];
      • Thus, the increase of the number of boomerangs follows the distance_prev_occurrences * 2.
    class Solution {
    public int numberOfBoomerangs(int[][] points) {
            if (points == null || points[0].length == 0) {
                return 0;
            }
    
            int counter = 0;
            Map<Double, Integer> mp = new HashMap<>();
    
            for (int i = 0; i < points.length; i++) {
                int[] main = points[i];
                for (int k = 0; k < points.length; k++) {
                    if (k != i) {
                        int[] sub = points[k];
                        double value = Math.pow(main[0] - sub[0], 2) + Math.pow(main[1] - sub[1], 2);
                        if (mp.containsKey(value)) {
                            int tmp = mp.get(value);
                            counter += tmp * 2;
                            mp.put(value, tmp + 1);
                        } else {
                            mp.put(value, 1);
                        }
                    }
                }
                mp = new HashMap<>();
            }
    
            return counter;
        }
    }
    

Log in to reply
 

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