|
| 1 | +packageeasy; |
| 2 | + |
| 3 | +importjava.util.HashMap; |
| 4 | +importjava.util.Map; |
| 5 | + |
| 6 | +publicclassNumberofBoomerangs { |
| 7 | +/**Looked at these two posts: https://discuss.leetcode.com/topic/66587/clean-java-solution-o-n-2-166ms and |
| 8 | + * https://discuss.leetcode.com/topic/66521/share-my-straightforward-solution-with-hashmap-o-n-2, basically, |
| 9 | + * have a HashMap, key is the distance, value is the number of points that are this distance apart to this point. |
| 10 | + * Note: we clear up this map every time after we traverse one point with the rest of the other points. |
| 11 | + * |
| 12 | + * Time complexity: O(n^2) |
| 13 | + * Space complexity: O(n)*/ |
| 14 | + |
| 15 | +publicintnumberOfBoomerangs(int[][]points) { |
| 16 | +intresult =0; |
| 17 | +if (points ==null ||points.length ==0 ||points[0].length ==0) |
| 18 | +returnresult; |
| 19 | +inttotalPts =points.length; |
| 20 | +Map<Long,Integer>map =newHashMap(); |
| 21 | +for (inti =0;i <totalPts;i++) { |
| 22 | +for (intj =0;j <totalPts;j++) { |
| 23 | +if (i ==j) |
| 24 | +continue; |
| 25 | +longd =calcDistance(points[i],points[j]); |
| 26 | +map.put(d,map.getOrDefault(d,0) +1); |
| 27 | + } |
| 28 | + |
| 29 | +for (intval :map.values()) { |
| 30 | +result +=val * (val -1); |
| 31 | + } |
| 32 | +map.clear(); |
| 33 | + } |
| 34 | +returnresult; |
| 35 | + } |
| 36 | + |
| 37 | +privatelongcalcDistance(int[]p1,int[]p2) { |
| 38 | +longx =p2[0] -p1[0]; |
| 39 | +longy =p2[1] -p1[1]; |
| 40 | +returnx *x +y *y; |
| 41 | + } |
| 42 | + |
| 43 | +publicstaticvoidmain(String...args) { |
| 44 | +NumberofBoomerangstest =newNumberofBoomerangs(); |
| 45 | +// int[][] points = new int[][]{ |
| 46 | +// {0,0}, |
| 47 | +// {1,0}, |
| 48 | +// {2,0}, |
| 49 | +// }; |
| 50 | + |
| 51 | +// [[3,6],[7,5],[3,5],[6,2],[9,1],[2,7],[0,9],[0,6],[2,6]], should return 10 |
| 52 | +int[][]points =newint[][] { {3,6 }, {7,5 }, {3,5 }, {6,2 }, {9,1 }, {2,7 }, |
| 53 | + {0,9 }, {0,6 }, {2,6 }, }; |
| 54 | + |
| 55 | +// [[0,0],[1,0],[-1,0],[0,1],[0,-1]] should return 20 |
| 56 | +System.out.println(test.numberOfBoomerangs(points)); |
| 57 | + } |
| 58 | +} |