1. 问题描述
描述:
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 jequals 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).
示例:
- 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]]
2. 问题分析
第一遍:
如果到点 a 的距离为 distance 的点共有 n 个, 那么从这 n 个点中有序找两个点就能与 A 点构成回旋, 根据排列公式, 总的回旋个数为 An2 个, 即 n * (n - 1) 个. 遍历每一个点, map 的 key 是距离, value 是距离该点 key 个单位的点的个数.
- class Solution {
- public int numberOfBoomerangs(int[][] points) {
- int res = 0;
- for(int i = 0; i <points.length; i++){
- Map<Double, Integer> map = new HashMap<>();
- for(int j = 0; j <points.length; j++){
- Double distance = Math.pow(points[i][0] - points[j][0], 2) + Math.pow(points[i][1] - points[j][1], 2);
- if(map.containsKey(distance)){
- map.put(distance, map.get(distance) + 1);
- }else{
- map.put(distance, 1);
- }
- }
- for(Integer count : map.values()){
- res += count * (count - 1);
- }
- }
- return res;
- }
- }
改进: 将 map 移到 for 循坏外, 之后每次外部循环结束后, 执行 map.clear() 操作. 不再每次都新建 map 集合.
- Map<Double, Integer> map = new HashMap<>();
- for(int i = 0; i < points.length; i++){
- for(int j = 0; j < points.length; j++){
- Double distance = Math.pow(points[i][0] - points[j][0], 2) + Math.pow(points[i][1] - points[j][1], 2);
- if(map.containsKey(distance)){
- map.put(distance, map.get(distance) + 1);
- }else{
- map.put(distance, 1);
- }
- }
- for(Integer count : map.values()){
- res += count * (count - 1);
- }
- map.clear();
- }
- View Code
来源: http://www.bubuko.com/infodetail-2978810.html