【Day 21 】2022-01-01 - 447. 回旋镖的数量

[azl397985856]

447. 回旋镖的数量

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/number-of-boomerangs/

前置知识

• 哈希表
• 两点间距离计算方法
• 排列组合基础知识

  题目描述

  
  给定平面上  n 对不同的点，“回旋镖” 是由点表示的元组  (i, j, k) ，其中  i  和  j  之间的距离和  i  和  k  之间的距离相等（需要考虑元组的顺序）。

找到所有回旋镖的数量。你可以假设  n 最大为 500，所有点的坐标在闭区间 [-10000, 10000] 中。

示例:

输入: [[0,0],[1,0],[2,0]]

输出: 2

解释: 两个回旋镖为 [[1,0],[0,0],[2,0]] 和 [[1,0],[2,0],[0,0]]

[yan0327]

思路： 哈希表+排列 本题的思路是找出三个回旋镖中，一个点到另外两个点的距离相同。=》记录过去的信息【哈希表擅长的事情】 首先遍历一遍回旋镖数组，并记录当前遍历到的回旋镖作为起始回旋镖 在循环内部初始化一个哈希表，重新遍历一遍回旋镖数组，并记录两个回旋镖之间的欧式距离。 循环结束后，遍历哈希表中距离的次数，然后利用数学的排列，从N个位置里面排列2个位置等于N*（N-1） 最终统计完就是最终答案。

func numberOfBoomerangs(points [][]int) int {
    out := 0
    for _,p := range points{
        count := map[int]int{}
        for _,q := range points{
            dis := (p[0]-q[0])*(p[0]-q[0]) + (p[1]-q[1])*(p[1]-q[1])
            count[dis]++
        }
        for _,x := range count{
            out += x * (x-1)
        }
    }
    return out
}

时间复杂度：O（N²） 空间复杂度：O（N）

[Bochengwan]

思路

对每个点 计算所有可能的距离，对于相同距离的回旋镖数量，为a*(a-1), a为那个距离的count。

代码

class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:

        def helper(a,b):
            return (a[0]-b[0])**2+(a[1]-b[1])**2
        if not points or len(points)<=2:
            return 0
        result = 0
        for p1 in points:
            my_mp = defaultdict(int)
            for p2 in points:
                my_mp[helper(p1,p2)]+=1
            for i in my_mp.values():
                result+=i*(i-1)
        return result

复杂度分析

• 时间复杂度：O(N^2)，其中 N 为数组长度。
• 空间复杂度：O(N)

[Toms-BigData]

【Day 21】447. 回旋镖的数量

思路

该题的任务解读后可知，其实就是求一个点为中心点时到该点的距离相等的点的个数的排列组合的和。简单的说就是距离为1的如果有两个，就是21，有3个就是32(A^2_n) 那就遍历数组，遍历时新建一个哈希表，存储每个点到该点的距离，再遍历哈希表，将value*（value-1）加到ans中，遍历结束后返回ans

golang代码

func numberOfBoomerangs(points [][]int) int {
    ans:=0
    for _,p := range points{
        cnt := make(map[int]int)
        for _,q := range points{
            dis :=calDistance(p[0],p[1],q[0],q[1])
            cnt[dis]++
        }
        for _,m:=range cnt{
            ans += m * (m-1)
        }
    }
    return ans
}
func calDistance(a1, a2, b1, b2 int) int {
    return (a1-b1)*(a1-b1)+(a2-b2)*(a2-b2)
}

复杂度

时间:O(n^2) 空间:O(n)

[Alfie100]

解题思路

暴力枚举。 枚举节点 point，计算到节点 point 距离相等的其他节点数目（记为 m），则以当前节点 point 为中心点可组成 m*(m-1) 个回旋镖。

Python 代码

class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:

        if len(points) < 3:
            return 0

        ans = 0
        for p in points:
            cnt = collections.Counter()
            for q in points:
                dist = (p[0]-q[0])**2 + (p[1]-q[1])**2
                cnt[dist] += 1
            for m in cnt.values():
                ans += m*(m-1)

        return ans

复杂度分析

• 时间复杂度：O(n^2)，其中 n 为点数。
• 空间复杂度：O(n)。

[charlestang]

思路

因为是有顺序的，所以，每个 point 都可以作为回旋镖的顶点，需要遍历。

任意 point 作为顶点的时候，出现至少两个点距离与顶点相同，才能组成回旋镖。我们遍历顶点之外的其余点与顶点的距离，并用 哈希 统计距离相等的点的数量。

假如有 n 个点与顶点距离相等，那么，第一个角点有 n 种可能，第二个角点有 n - 1 种可能，总共有 n * (n -1) 种可能。

这个数字恰好等于 1 + 2 + ... + (n -1) 的和的两倍（这个事实有利于迭代计算解的总数）。

代码

class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:
        n, ans = len(points), 0
        if n < 3: return 0
        for x1, y1 in points:
            freq = Counter()
            for x2, y2 in points:
                dx, dy = x1 - x2, y1 - y2
                dis = dx * dx + dy * dy
                if dis not in freq:
                    freq[dis] = 1
                else:
                    ans += freq[dis]
                    freq[dis] += 1 
        return ans * 2

时间复杂度 O(n^2)

空间复杂度 O(n)

[Liuxy94]

思路

第一反应是暴力解，看了一下题解可以哈希表优化 思路就是哈希+排列组合

代码

class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:
        n = len(points)
        ans = 0
        for i in range(n):
            m = collections.defaultdict(int)
            for j in range(n):
                dist = abs(points[i][0] - points[j][0]) ** 2 + abs(points[i][1] - points[j][1]) ** 2
                m[dist] += 1
            for count in m.values():
                ans += count * (count-1)
        return ans

复杂度

时间 O(n^2)

空间 O(n)

[Davont]

code

/**
 * @param {number[][]} points
 * @return {number}
 */
var numberOfBoomerangs = function(points) {
  let ans = 0;
  for (let i = 0; i < points.length; i++) {    
    let map = new Map();
    for (let j = 0; j < points.length; j++) {
      if (i === j) continue;
      const dist = (points[i][0] - points[j][0])**2 + (points[i][1] - points[j][1])**2;
      if (map.has(dist)) {
        map.set(dist, [...map.get(dist), [points[j][0], points[j][1]]]);
      } else {
        map.set(dist, [[points[j][0], points[j][1]]]);
      }
    }
    for (const [key, val] of map) {
      ans += val.length * (val.length - 1);
    }
  }
  return ans;
};

[zwmanman]

class Solution(object): def numberOfBoomerangs(self, points): """ :type points: List[List[int]] :rtype: int """ n = len(points) res = 0

    for i in range(n):
        helperDict = collections.defaultdict(int)
        for j in range(n):
            distance = (points[i][0] - points[j][0]) ** 2 + (points[i][1] - points[j][1]) ** 2
            helperDict[distance] += 1
        for count in helperDict.values():
            res += count * (count - 1)

    return res

[ZacheryCao]

Idea

Hash Table. Two loops. Outer loop scan the array from beginning to the end. inner loop scan the array to get the distance between current point in this loop and the point in outer loop. If the distance in the hash table update the amount by one, otherwise initialize the distance in the hash table and its value to 1. After the inner loop finishes, scan through the hash table to add answer by n*(n-1). n is the value (amount of pair) for each distance in the hash table. Then reset the hash table, continue the outer looper

Code

class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:
        ans = 0
        for i in range(len(points)):
            seen = {}
            x1, y1 = points[i]
            for j in range(len(points)):
                if i ==j:
                    continue
                x2, y2 = points[j]
                d = (x1 - x2)**2 + (y1-y2)**2
                seen[d] = seen.get(d, 0) + 1
            for d in seen:
                ans += seen[d]*(seen[d] - 1)
        return ans

Complexity:

Time: O(N^2) Space: O(N)

[rzhao010]

Thoughts

1. In the outer loop, we traverse each point in the array
2. in each traverse, we traverse the rest points, calculate the distance between the first and second points, save <distance, count> into a HashMap, so if we get a same distance, count++
3. add up count * (count - 1) is the answer

Code

    public int numberOfBoomerangs(int[][] points) {
        int n = points.length;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            Map<Integer, Integer> map = new HashMap<>();
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                int x = points[i][0] - points[j][0];
                int y = points[i][1] - points[j][1];
                int dist = x * x + y * y;
                map.put(dist, map.getOrDefault(dist, 0) + 1);
            }
            for (int dis: map.keySet()) {
                int count = map.get(dis);
                ans += count * (count - 1);
            }
        }
        return ans;
    }

Complexity

• Time: O(n) nested loop
• Space: O(n) hashmap used

[laofuWF]

# use a dict to track how other points distance from given point
# iterate values and add count * (count - 1) to res (permutation)
# time: O(N^2)
# space: O(N)

class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:
        if len(points) < 3:
            return 0

        res = 0
        for i1, p1 in enumerate(points):
            distance = {}
            for i2, p2 in enumerate(points):
                if i1 == i2: 
                    continue

                curr_dist = (p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2
                distance[curr_dist] = distance.get(curr_dist, 0) + 1

            for count in distance.values():
                if count > 1:
                    res += count * (count - 1)

        return res

[xj-yan]

class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:
        res = 0
        for p in points:
            d = dict()
            for q in points:
                x = p[0] - q[0]
                y = p[1] - q[1]
                d[x * x + y * y] = d.get(x * x + y * y, 0) + 1
            for k in d:
                res += d[k] * (d[k] - 1)
        return res

Time Complexity: o(n^2), Space Complexity: O(n)

[zjsuper]

class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:
        ans =0

        for i in range(len(points)):
            #use distance as key
            dis = defaultdict(int)
            for j in range(len(points)):
                dist = (points[i][0]-points[j][0])**2 + (points[i][1]-points[j][1])**2
                dis[dist] += 1
            for d in dis.keys():
                ans += dis[d]*(dis[d]-1)

        return ans

[zhangzz2015]

思路

• 分析题目，关键是[ i, j, k] i 到 j 的距离和i 到k 的距离相等，则组成一个回旋镖，进一步转化问题，当固定 i ，找到所有距离相等的点有n个，能形成多个个回旋镖，为组合数，n(n-1)个。使用hash map 记录相同点的个数。具体思路为，两层遍历，第一层遍历i, 第二层遍历 j ，找到到i 相同的distance 的个数，完成后进行计算 n(n-1)。时间复杂度为O(n^2)，空间复杂度为O(n)。

关键点

代码

• 语言支持：C++

C++ Code:

class Solution {
public:
    int numberOfBoomerangs(vector<vector<int>>& points) {

        //  
        int ret =0; 
        for(int i=0; i< points.size(); i++)
        {
            unordered_map<int, int> record;                     
            for(int j=0; j< points.size(); j++)
            {

                if(j ==i ) continue; 
                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]); 

                record[dis]++; 
            }            
            for(auto it = record.begin(); it != record.end(); it++)
            {
                int iSize = (*it).second;                 
                ret += ((iSize)*(iSize-1)); 
            }             
        }                   
        return ret;         
    }
};

[cszys888]

class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:
        from collections import defaultdict
        result = 0
        for point in points:
            count = defaultdict(int)
            for point_x in points:
                if point_x == point:
                    continue
                else:
                    dis =  (point_x[0] - point[0])**2 + (point_x[1] - point[1])**2
                    count[dis] += 1
            for cnt in count.values():
                result += cnt*(cnt - 1)
        return result

time complexity: O(N^2) space complexity: O(N)

[LannyX]

思路

Hash Map

代码

class Solution {
    public int numberOfBoomerangs(int[][] points) {
        if(points == null || points.length <= 2){
            return 0;
        }
        Map<Integer, Integer> map = new HashMap<>();
        int res = 0;
        for(int i = 0; i < points.length; i++){
            for(int j = 0; j < points.length; j++){
                int dis = getDistance(points[i], points[j]);
                map.put(dis, map.getOrDefault(dis, 0) + 1);
            }
            for(int n: map.values()){
                res += n * (n - 1);
            }
            map.clear();
        }

        return res;
    }
    private int getDistance(int[] x, int[] y){
        int x1 = y[0] - x[0];
        int y1 = y[1] - x[1];

        return x1 * x1 + y1* y1;
    }
}

复杂度分析

• 时间复杂度：O(N2)
• 空间复杂度：O(N)

[wangzehan123]

• 语言支持：Java

Java Code:

public class Solution {
    private int getDistance(int[] a, int[] b) {
        int dx = a[0] - b[0];
        int dy = a[1] - b[1];
        return dx * dx + dy * dy;
    }

    public int numberOfBoomerangs(int[][] points) {
        if (points == null) {
            return 0;
        }
        int ans = 0;
        for (int i = 0; i < points.length; i++) {
            Map<Integer, Integer> disCount = new HashMap<>();
            for (int j = 0; j < points.length; j++) {
                if (i == j) {
                    continue;
                }
                int distance = getDistance(points[i], points[j]);
                int count = disCount.getOrDefault(distance, 0);
                disCount.put(distance, count + 1);
            }
            for (int count : disCount.values()) {
                ans += count * (count - 1);
            }
        }
        return ans;
    }
}

[feifan-bai]

思路

1. 可以遍历points, 统计两点之间的距离，
2. 相同距离的点有m个, 则组合可能性为m * (m-1)
3. ans = 所有可能距离对应的m (m-1)求和 代码*

   class Solution:
   def numberOfBoomerangs(self, points: List[List[int]]) -> int:
       ans = 0
       for p in points:
           cnt = Counter()
           for q in points:
               dis = (p[0] - q[0]) ** 2 + (p[1] - q[1]) ** 2
               cnt[dis] += 1
           for val in cnt.values():
               ans += val * (val-1)
       return ans

   复杂度分析

   • 时间复杂度：O(N ^ 2)
   • 空间复杂度：O(N)

[herbertpan]

思路

1. 确实一开始比较没思路，直觉上的确是算distance，用hashmap把相等的distance放在一起，然后算个数。但感觉就这算法是不是太简单了。
2. 算distance比较没难度，我觉得难点在于怎么知道5个points对应20个boomerang。我是没有相当 5 * 4 = 20。 相应的，我就做了个check array，直接取表就可以了

Code

public int numberOfBoomerangs(int[][] points) {
        // corner case: at least has 3 points to make a boomerang
        if (points.length < 3) {
            return 0;
        }

        int result = 0;

        // build check arr
        int[] checkArr = new int[points.length];
        checkArr[0] = 0;
        checkArr[1] = 0;
        checkArr[2] = 2;
        for (int i = 3; i < checkArr.length; i++) {
            checkArr[i] = (checkArr[i - 1] / 2 + i - 1) * 2;
        }

        // build distance row for pointI 
        double[] distances = new double[points.length];

        for (int i = 0; i < points.length; i++) {
            // calculate point i to other points distance
            int pointIX = points[i][0];
            int pointIY = points[i][1];

            Map<Double, Integer> distanceToNumberOfPoints = new HashMap<>();

            for (int j = 0; j < points.length; j++) {
                int pointJX = points[j][0];
                int pointJY = points[j][1];
                double distance = Math.pow(pointIX - pointJX, 2) + Math.pow(pointIY - pointJY, 2);              
                distanceToNumberOfPoints.put(distance, distanceToNumberOfPoints.getOrDefault(distance, 0) + 1);
            }

            // now we can check the boomerang for this line
            int resultForPointI = 0;
            // after check the row lets calcluate how many boomerang
            for (Map.Entry<Double, Integer> entry : distanceToNumberOfPoints.entrySet()) {
                resultForPointI += checkArr[entry.getValue()];
            }

            result += resultForPointI;
        }

        return result;
    }

Complexity

1.time : O(n^2)

2. space: O(N)

[Husky-Gong]

class Solution {
    public int numberOfBoomerangs(int[][] points) {
        if(points ==null || points.length==0) return 0;
        // <distance, count>
        HashMap<Integer,Integer> map = new HashMap<>();
        int res = 0;

        for(int i=0; i<points.length; i++){
            for(int j=0; j<points.length; j++){
                if(i==j) continue;
                int distance = getDistance(points[i], points[j]);
                map.put(distance, map.getOrDefault(distance,0)+1);
            }
            for(int val:map.values()){
                res+=val*(val-1);
            }
            map.clear();
        }
        return res;
    }

    private int getDistance(int[] i, int[] j){
        return (i[0]-j[0])*(i[0]-j[0])+(i[1]-j[1])*(i[1]-j[1]);
    }
}

[wxj783428795]

思路

1. 双层循环，内层循环计算每个点与外层点的距离，并用哈希表保存，距离以及距离相同的点的个数
2. 总的次数为 个数*（个数-1），累加即可。

代码

var numberOfBoomerangs = function (points) {
    let ans = 0;
    for (let p1 of points) {
        let map = {};
        for (let p2 of points) {
            let dis = getDistance(p1, p2);
            if (map[dis] === undefined) {
                map[dis] = 1;
            } else {
                map[dis] += 1
            }
        }
        Object.entries(map).forEach(([k, v]) => {
            ans += v * (v - 1)
        })
    }
    return ans
};

var getDistance = (p1, p2) => {
    return Math.pow(p1[0] - p2[0], 2) + Math.pow(p1[1] - p2[1],2);
}

复杂度分析

复杂度分析不是很会，不一定对，如果有错，请指正。

• 时间复杂度：O(n²)
• 空间复杂度：O(n)

[li65943930]

public int numberOfBoomerangs(int[][] points) {

if (points == null || points.length <= 2)
    return 0;

int res = 0;
Map<Integer, Integer> equalCount = new HashMap<>();

for (int i = 0; i < points.length; ++i) {

    for (int j = 0; j < points.length; ++j) {

        int dinstance = getDistance(points[i], points[j]);
        equalCount.put(dinstance, equalCount.getOrDefault(dinstance, 0) + 1);
    }

    for (int count : equalCount.values())
        res += count * (count - 1);
    equalCount.clear();
}

return res;

}

private int getDistance(int[] x, int[] y) {

int x1 = y[0] - x[0];
int y1 = y[1] - x[1];

return x1 * x1 + y1 * y1;

}

[YuyingLiu2021]

class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:
        #distance用欧氏距离
        n = len(points)
        if n < 3:
            return 0

        def dist(p1, p2):
            return (p1[0] - p2[0])*(p1[0] - p2[0]) + (p1[1] - p2[1])*(p1[1] - p2[1])
        #计算每两点之间的距离

        ans = 0
        for i in range(n):
            cnt = collections.Counter()#collections库中非常好用的字典子类，用于计数
            for j in range(n):
                dis = dist(points[i] , points[j])
                cnt[dis] += 1

            for x in cnt.values():
                ans +=math.perm(x, 2)#math库中的排列函数

        return ans

[Frederickfan]

public int numberOfBoomerangs(int[][] p) {
        int n = p.length;
        if(n==0) return 0;
        int count = 0;
        for(int i=0;i<n;i++){
            Map<Double,Integer> map = new HashMap<>();
            for(int j=0;j<n;j++){
                if(map.containsKey(distance(p[i],p[j]))){
                    int value = map.get(distance(p[i],p[j]));
                    count+=2*value;
                    map.put(distance(p[i],p[j]),value+1);
                } else {
                    map.put(distance(p[i],p[j]),1);
                }
            }
        }
        return count;
    }

    public Double distance(int[] a, int[]b){
        return Math.sqrt(Math.pow(a[0]-b[0],2) + Math.pow(a[1]-b[1],2));
    }

[tongxw]

思路

关键是看懂题目在问什么。。

代码

class Solution {
    public int numberOfBoomerangs(int[][] points) {
        int n = points.length;
        int total = 0;
        for (int i=0; i<n; i++) {
            int x = points[i][0];
            int y = points[i][1];
            Map<Integer, Integer> distCnt = new HashMap<>(); // 统计其他点到点i的距离
            for (int j=0; j<n; j++) {
                if (i == j) {
                    continue;
                }
                int x1 = points[j][0];
                int y1 = points[j][1];
                int dist = (x - x1) * (x - x1) + (y - y1) * (y - y1);
                distCnt.put(dist, distCnt.getOrDefault(dist, 0) + 1);
            }

            // 假设有n个点到点i距离相同，那么以点i为顶点的等腰三角形数量是n取2的排列数 = n * (n-1)
            for (int count : distCnt.values()) {
                total += count * (count - 1);
            }
        }

        return total;
    }
}

SC: O(N^2) TC: O(N)

[watchpoints]

思路

新题目

代码

class Solution {
public:
    int numberOfBoomerangs(vector<vector<int>>& po) {
        int num=0;
    for(auto a:po){
        unordered_map<int,int>ha;
        for(auto b:po){
            int len=(a[0]-b[0])*(a[0]-b[0])+(a[1]-b[1])*(a[1]-b[1]); //这里没必要带根号，直接存即可
            ha[len]++;
        }
        for(auto i:ha)
        num+=i.second*(i.second-1);
    }
    return num;
    }
};

[moirobinzhang]

Code:

public class Solution { public int NumberOfBoomerangs(int[][] points) { if (points == null || points.Length <= 2) return 0;

    int len = points.Length;
    int result = 0;

    for (int i = 0; i < len; i++)
    {
        Dictionary<int, int> distanceDict = new Dictionary<int, int>();

        for (int j = 0; j < len; j++)
        {
            if (i == j)
                continue;

            int tempDistance = GetDistance(points[i], points[j]);
            if (!distanceDict.ContainsKey(tempDistance))
                distanceDict.Add(tempDistance, 0);

            distanceDict[tempDistance]++;                    
        }

        foreach(int count in distanceDict.Values)
            result += count * (count - 1);
    }

    return result;        
}

public int GetDistance(int[] p1, int[] p2)
{
    var d0 = p1[0] - p2[0];
    var d1 = p1[1] - p2[1];
    return d0 * d0 + d1 * d1;
}

}

[Leonalhq]

class Solution(object): def decodeString(self, s): """ :type s: str :rtype: str """ res = [] temp = "" times = 0

    for curr in s:
        if curr.isdigit():
            times = times*10 + int(curr)
        elif curr == '[':
            #如何处理押宅,如何遇到第一格,第二个格
            res.append(temp)
            res.append(times)
            temp=""
            times = 0
        elif curr == ']':
            if len(res):
                num,strs = res.pop(), res.pop()
                temp=strs+num*temp
        else:
            temp+=curr

    return temp

[callmeerika]

思路

遍历数组，找出与当前点距离一样的点的数量，然后求组合数，累加，这就是当前点对应的所有回旋镖数量

代码

var numberOfBoomerangs = function(points) {
    let num = 0;
    points.forEach(v=>{
        let hash = new Map();
        points.forEach(w=>{
            let distance = Math.pow(v[0]-w[0],2) + Math.pow(v[1]-w[1],2);
            hash.set(distance,(hash.get(distance)||0) + 1);
        })
        let arr = hash.values();
        [...arr].forEach(vv=>{
            num = num + vv*(vv-1)
        })
    })
    return num
};

复杂度

时间复杂度：O(n^2)
空间复杂度：O(n)

[Myleswork]

思路

两层循环，第一层确定中间点i，并构建哈希表用于存储相同距离节点个数；第二层遍历其余所有节点，计算欧氏距离并存储到哈希表中。第二层循环跳出后按照排列组合计算可以过程的回旋镖的个数，并计入总数。

代码

class Solution {
public:
    int numberOfBoomerangs(vector<vector<int>>& points) {
        int sum = 0;
        for(int i = 0;i<points.size();i++){
            unordered_map<int,int> dis; //存储第i个节点出发的相同距离的节点的个数
            for(int j = 0;j<points.size();j++){
                if(i == j) continue;
                int curdis = pow((points[i][0]-points[j][0]),2)+pow((points[i][1]-points[j][1]),2);
                dis[curdis]++;
            }
            //计算以第i个节点为i时能够构成的回旋镖的数量
            for(auto it = dis.begin();it!=dis.end();it++){
                sum = sum + (it->second*(it->second-1));
            }
        }
        return sum;
    }
};

复杂度分析

时间复杂度：O(n^2) 两层循环

空间复杂度：O(n) 最坏的情况，所有节点之间的距离都不一样

[spacker-343]

思路

遍历每个点，然后用hash表统计这个点到每个点的距离，最后用计算排列数的公式算出排列数

代码

class Solution {
    public int numberOfBoomerangs(int[][] points) {
        int n = points.length;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            Map<Integer, Integer> map = new HashMap<>();
            // 该点到每个点的距离
            for (int j = 0; j < n; j++) {
                if (i == j) {
                    continue;
                }
                int x = points[i][0] - points[j][0];
                int y = points[i][1] - points[j][1];
                int dis = x * x + y * y;
                map.put(dis, map.getOrDefault(dis, 0) + 1);
            }
            for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
                // 排列数计算公式，A(n, 2) 等于 n * n - 1
                ans += entry.getValue() * (entry.getValue() - 1);
            }
        }
        return ans;
    }
}

复杂度

时间复杂度：O(n^2) 空间复杂度：O(n)

[zhangyalei1026]

class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:
        ans = 0
        for x1, y1 in points:
            cnts = defaultdict(int)
            for x2, y2 in points:
                dx, dy = x1 - x2, y1 - y2
                d = dx * dx + dy * dy
                ans += cnts[d]
                cnts[d] += 1
        return ans * 2

[Flower-F]

解题思路

哈希 + 排列组合

代码

/**
 * @param {number[][]} points
 * @return {number}
 */
var numberOfBoomerangs = function (points) {
    const len = points.length;
    if (len < 3) {
        return 0;
    }

    let ans = 0;
    for (let i = 0; i < len; i++) {
        const map = new Map();
        for (let j = 0; j < len; j++) {
            const dis = dis2(points[i], points[j]);
            map.set(dis, (map.get(dis) || 0) + 1);
        }
        map.forEach(value => {
            // 排列组合
            // A(n, 2)
            ans += value * (value - 1);
        })
    }

    return ans;

    function dis2(p1, p2) {
        return (p1[0] - p2[0]) * (p1[0] - p2[0]) + (p1[1] - p2[1]) * (p1[1] - p2[1]);
    }
};

复杂度

时间：O(N ^ 2) 空间：O(N)

[Alexno1no2]

# 暴力破解
# 对每一个点，统计其他点到该点的距离，假如有n个点到该点距离了相等，则有n * (n-1)种组合

#复杂度分析
#时间 O(N^2) 
#控件 O(N)

class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:
        def distance(p1, p2):
            return (p1[0] - p2[0]) * (p1[0] - p2[0]) + (p1[1] - p2[1]) * (p1[1] - p2[1])

        res = 0
        for p in points:
            cnts = collections.defaultdict(int)
            for q in points:
                cnts[distance(p, q)] += 1

            for n in cnts.values():
                res += n * (n - 1)
        return res

[a244629128]

var numberOfBoomerangs = function(points) {
    let res = 0;
    for(let i = 0; i<points.length;i++){
        let map = {};
        for(let j = 0; j<points.length;j++){
            if(i === j){
                continue;
            }
            const dist = Math.abs(points[i][0]-points[j][0])**2 + Math.abs(points[i][1]-points[j][1])**2;

            if(map[dist]){
                res += map[dist]*2;
                map[dist]++;
            }else{
                 map[dist] = 1;
            }

       }
    }
    return res;
};

[chen445]

代码

var numberOfBoomerangs = function(points) {
    let result=0
    for(let i=0; i<points.length; i++){
        let map={}
        for(let j=0; j< points.length;j++){
            if(i!==j){
                let dis=find_two_points_dis(points[i],points[j])
                if(map[dis]=== undefined){
                    map[dis]=1
                }else{
                    map[dis]+=1
                }
            }
        }
        Object.values(map).forEach(val => {
            if(val>1){
                result+=val*(val-1)
            }
        })
    }
    return result
};

let find_two_points_dis= function(point1,point2){
    return (point1[0]-point2[0])**2+(point1[1]-point2[1])**2
}

复杂度

Time: O(n^2)

Space: O(n)

[haixiaolu]

思路：参考 “machelle” 题解

哈希表

• 遍历每个元组的点
• 两点间的距离公式 （为了节省时间， 可以不用平方根）
• 检查两点间的距离是否在哈希表中 -- 在的话， append to resulte -- 不在的话， 设置距离为1
• 返回 result * 2

代码 / Python

class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:

        result = 0

        for x1, y1 in points:
            hashmap = {}

            for x2, y2 in points:
                if x1 == x2 and y1 == y2:
                    continue

                # 两点之间的距离
                dx = x1 - x2
                dy = y1 - y2
                d = dx * dx + dy * dy

                if d in hashmap:
                    result += hashmap[d]
                    hashmap[d] += 1    
                else:
                    hashmap[d] = 1

        return result * 2

复杂度分析：

• 时间复杂度： O(n^2)
• 空间复杂度： O(n)

[tian-pengfei]

class Solution {
public:
//k这个点也在point里面呢，理解题意很关键.
    int numberOfBoomerangs(vector<vector<int>>& points) {

        int num=0;

        for(int i=0; i<points.size();i++){
            int x_i = points[i][0];
            int y_i = points[i][1];
            map<double,int> i_point;

            for(int j=0;j<points.size();j++){
                if(i==j){
                    continue;
                }
                int x_j = points[j][0];
                int y_j = points[j][1];
                double dis  = pow(x_i-x_j,2)+pow(y_i-y_j,2);
                if(i_point.find(dis)!=i_point.end()){
                    i_point[dis] = ++i_point[dis];
                }else{
                    i_point[dis] = 1;
                }

            }
            for(auto const &[dis,count]:i_point){
                if(count==1){
                    continue;
                } else{
                    num+=(count-1)*count;
                }
            }

        }

        return num;

    }
};

[Tesla-1i]

class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:
        ans = 0
        for p in points:
            cnt = Counter()
            for q in points:
                dis = (p[0] - q[0]) ** 2 + (p[1] - q[1]) ** 2
                cnt[dis] += 1
            for val in cnt.values():
                ans += val * (val-1)
        return ans

[Richard-LYF]

class Solution: def numberOfBoomerangs(self, points: List[List[int]]) -> int:

    ans = 0

    for p in points:
        c = {}
        for q in points:
            dis = (p[0] - q[0])**2 + (p[1] - q[1])**2
            if dis in c:
                c[dis] +=1
            else:
                c[dis] = 1
        for m in c.values():
            ans += m * (m - 1)
    return ans

o n2 o n

[BpointA]

思路

以出发点+距离List做哈希表的Key，计数。再遍历计数，取其中两两组合的数量。

Java代码

class Solution {
    public int numberOfBoomerangs(int[][] points) {
        HashMap<List<Integer>,Integer> dist=new HashMap<>();
        int m=points.length;
        for(int i=0;i<m;i++)
        {
        for(int j=i+1;j<m;j++)
        {
            int x1=points[i][0];
            int y1=points[i][1];
            int x2=points[j][0];
            int y2=points[j][1];
            int l=(y2-y1)*(y2-y1)+(x2-x1)*(x2-x1);
            List<Integer> tmp1=new ArrayList<>();
            tmp1.add(i);
            tmp1.add(l);
            List<Integer> tmp2=new ArrayList<>();
            tmp2.add(j);
            tmp2.add(l);
            dist.put(tmp1,dist.getOrDefault(tmp1,0)+1);
            dist.put(tmp2,dist.getOrDefault(tmp2,0)+1);

        }
        }
        int ans=0;
        for (int aa:dist.values())
        {
            ans+=aa*(aa-1);
        }
        return ans;

    }
}

[ZhangNN2018]

思路

• 哈希表

复杂度

• 时间复杂度: O(n^2)
• 空间复杂度: O(n)

代码

 class Solution(object):
    def numberOfBoomerangs(self, points):
        """
        :type points: List[List[int]]
        :rtype: int
        """
        result=0
        for m in points:
            dic={}
            for j in points:
                distance=(m[0]-j[0])**2+(m[1]-j[1])**2
                if distance not in dic:
                    dic[distance]=1
                else:
                    dic[distance]+=1
            for val in dic.values():
                if val>=2:
                    result+=val*(val-1)
        return result

[bluetomlee]

思路

枚举

解法

class Solution {
public:
    int numberOfBoomerangs(vector<vector<int>> &points) {
        int ans = 0;
        for (auto &p : points) {
            unordered_map<int, int> cnt;
            for (auto &q : points) {
                int dis = (p[0] - q[0]) * (p[0] - q[0]) + (p[1] - q[1]) * (p[1] - q[1]);
                ++cnt[dis];
            }
            for (auto &[_, m] : cnt) {
                ans += m * (m - 1);
            }
        }
        return ans;
    }
};

[biscuit279]

思路：

对每个数都统计一下跟其他数的距离，存入哈希表中

class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:

        ans = 0
        num = len(points)
        for i in range(num):
            dis_dict = {}
            for j in range(num):
                dis = abs(points[i][0]-points[j][0])**2 + abs(points[i][1] - points[j][1]) **2
                if dis not in dis_dict:
                    dis_dict[dis] = 1
                else:    
                    dis_dict[dis] += 1
            for val in dis_dict.values():
                ans += val*(val-1)
        return ans

时间复杂度：O（n2） 空间复杂度：O（n2）

[zol013]

class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:
        ans = 0
        for i in range(len(points)):
            hashmap = defaultdict(int)
            for j in range(len(points)):
                dist = (points[i][0] - points[j][0]) ** 2 + (points[i][1] - points[j][1]) ** 2
                if dist != 0:
                    hashmap[dist] += 1
            for dist, cnt in hashmap.items():
                ans += cnt * (cnt - 1)

        return ans

TC : O(N^2) SC: O(N)

[z1ggy-o]

思路

基本思路是每次以一个点为始发点，计算它和其他点的距离。如果有相同的距离，则可以组成一个 boomerang。 直接暴力解的话会有许多的重复计算。我们可以将计算过的结果存放起来，从而降低复杂度。

因为只要求回答个数，我们可以记录点的信息，也可以不记录。 不记录点信息的写法更简洁，使用排列的数学公式计算即可。

代码

CPP 不记录点，只计算排列可能性。

class Solution {
public:
    int numberOfBoomerangs(vector<vector<int>>& points) {
        if (points.size() < 3) return 0;

        int ret = 0;
        for (auto &p : points) {
            unordered_map<int, int> cnt;  // <distance, count>
            for (auto &q: points) {
                int dst = (p[0] - q[0]) * (p[0] - q[0]) + (p[1] - q[1]) * (p[1] - q[1]);
                cnt[dst]++;
            }
            for (auto &[_, v] : cnt) {  // permutation
                ret += v * (v-1);
            }
        }
        return ret;
    }
};

复杂度分析

• 时间：O(n^2). 对每个点，都遍历一次其他点
• 空间：O(n). 最差情况下每两个点之间的距离都不同

[baddate]

题目

https://leetcode-cn.com/problems/number-of-boomerangs/

思路

枚举+哈希表：

首先遍历数组，统计到每个点points[i]的距离，并写入哈希表，然后遍历哈希表统计个数。

代码

class Solution {
public:
    int numberOfBoomerangs(vector<vector<int>> &points) {
        int ans = 0;
        for (auto &p : points) {
            unordered_map<int, int> cnt;
            for (auto &q : points) {
                int dis = (p[0] - q[0]) * (p[0] - q[0]) + (p[1] - q[1]) * (p[1] - q[1]);
                ++cnt[dis];
            }
            for (auto &[_, m] : cnt) {
                ans += m * (m - 1);
            }
        }
        return ans;
    }
};

复杂度分析

• 时间复杂度：O(N^2)，其中N是数组 points 的长度。
• 空间复杂度：O(N)

[ggohem]

思路：

枚举+哈希表

代码：

class Solution {
    public int numberOfBoomerangs(int[][] points) {
        int ans = 0;
        for (int[] p : points) {
            Map<Integer, Integer> cnt = new HashMap<Integer, Integer>();
            for (int[] q : points) {
                int dis = (p[0] - q[0]) * (p[0] - q[0]) + (p[1] - q[1]) * (p[1] - q[1]);
                cnt.put(dis, cnt.getOrDefault(dis, 0) + 1);
            }
            for (Map.Entry<Integer, Integer> entry : cnt.entrySet()) {
                int m = entry.getValue();
                ans += m * (m - 1);
            }
        }
        return ans;
    }
}

时空复杂度：

• 时间复杂度：O(n^2)
• 空间复杂度：O(n)

[hdyhdy]

思路：使用map记录相同距离的数量，那么当前节点p可以与之前相同距离dist的节点的组合出回旋镖。

与每一个都可以组合，且不考虑顺序，那么当前节点可以组合的数量为map[dist] * 2。

func numberOfBoomerangs(points [][]int) int {
    var res int
    for _, p1 := range points {
        cnt := map[int]int{}
        for _, p2 := range points {
            dist := (p1[0] - p2[0]) * (p1[0] - p2[0]) + (p1[1] - p2[1]) * (p1[1] - p2[1])
            res += cnt[dist] * 2
            cnt[dist]++
        }
    }
    return res
}

时间复杂度：n2 空间，n

[1149004121]

447. 回旋镖的数量

思路

回旋镖就是中间节点到两侧节点有相同距离的组合，(中间，左，右)、(中间、右、左)记为2个回旋镖。考虑用哈希表保存到该中间节点的所有距离，则以中间节点为中心的回旋镖数量等于∑m（m-1），m为某距离的个数。遍历数组中所有节点，以其为中间节点的所有回旋镖数量即为结果。

代码

    var numberOfBoomerangs = function(points) {
        let ans = 0;
        for(const p1 of points){
            let map = new Map();
            for(const p2 of points){
                let dis = (p1[0] - p2[0]) * (p1[0] - p2[0]) + (p1[1] - p2[1]) * (p1[1] - p2[1]);
                map.set(dis, (map.get(dis) || 0) + 1);
            };
            for(const times of map.values()){
                ans += times * (times - 1);
            }
        };
        return ans;
    };

复杂度分析

• 时间复杂度：O(N^2)。
• 空间复杂度：O(N)。