【Day 21 】2021-09-30 - 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]]

[yanglr]

思路

理解题意:

回旋镖 是由点 (i, j, k) 表示的三元组 ，其中 i 和 j 之间的距离和 i 和 k 之间的距离相等（需要考虑元组的顺序）, 不妨称 i 为标杆元素。

例如, 比如有两个点b, c到点a (标杆元素, 应该放在结果三元组中第一个位置) 的距离是相同的, 那么满足要求的三元组有 abc 和 acb, 共P(2, 2) = 2个回旋镖。 再比如假如 p1, p2, p3 与 p0 (标杆元素, 应该放在结果三元组中第一个位置) 的距离相同, 那么有 P(3, 2) = 3 * (3-1) = 6 个回旋镖

(p1, p0, p2), (p1, p0, p3)

(p2, p0, p1), (p2, p0, p3)

(p3, p0, p1), (p3, p0, p2) ...

于是我们可以发现规律：如果有 k 个点与当前点具有相同的距离, 则可新产生 P(k, 2) = k*(k-1) 个回旋镖。

数据范围: n = points.length, n: [1, 500]

方法1：哈希表

遍历原points数组，每一趟能取到一个点，每趟维护一个与之相关的新的哈希表。 对于每个点, 用一个计数的哈希表来保存这个点与其它点的不同距离的数量。

接下来，遍历哈希表，累加每一趟的value*(value-1) 就能得到最终结果。

代码

实现语言: C++

class Solution {
public:
    int numberOfBoomerangs(vector<vector<int>>& points) {
        // n = points.length, n: [1, 500]
        const int n = points.size();
        int res = 0;
        for (int i = 0; i < n; i++)
        {
            unordered_map<int, int> dict;
            for (int j = 0; j < n; j++)
            {
                const int dx = points[j][0] - points[i][0];
                const int dy = points[j][1] - points[i][1];
                long long d = dx*dx + dy*dy;
                if (i != j) dict[d]++; // 去重
            }            
            for (auto& [k, c] : dict)
                res += c*(c-1);               
        }

        return res;   
    }
};

复杂度分析

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

方法2：排序

遍历原points数组，每一趟能取到一个点，每趟维护一个与之相关的新的数组，用于存放每两个点之间距离的平方。 然后对数组进行排序，那么相等的数会出现在相邻位置，此时用双指针统计各个距离出现次数，再累加每一趟的value*(value-1) 就能得到最终结果。

dist = [1, 2, 1, 2, 1, 5]

sorted_dist = [1, 1, 1, 2, 2, 5], 1*3, 2*2, 5*1

res = 3*(3-1) + 2 * (2 - 1) + 1 * (1 - 1) = 8

代码

实现语言: C++

class Solution {
public:
    int numberOfBoomerangs(vector<vector<int>>& points) {
        // n = points.length, n: [1, 500]
        const int n = points.size();
        int res = 0;
        for (int i = 0; i < n; i++)
        {
            vector<int> dists(n);
            for (int j = 0; j < n; j++)
            {
                const int dx = points[j][0] - points[i][0];
                const int dy = points[j][1] - points[i][1];
                dists[j] = dx * dx + dy * dy;
            }
            sort(dists.begin(), dists.end());
            for (int k = 1; k < n; k++)
            {
                int p = 1;
                while (k < n && dists[k] == dists[k - 1])
                {
                    k++;
                    p++;
                }
                res += p * (p - 1);
            }
        }
        return res;
    }
};

复杂度分析

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

[leungogogo]

LC447. Number of Boomerangs

Method. Hash + Counting

Main Idea

Brute force is to use 3 nested loops, but obviously it will cause TLE.

For each element in the input array, we can set it as the first point in tuple, and we calculate the distance from it to all other points, and use a map to record the count. So map[k] = cnt means there are cnt points with distance k from the first point.

Once we have all the counts, iterate through the distances, if there are cnt points with distance k to the first point, it can form cnt * (cnt - 1) pairs.

Code

• CPP

class Solution {
public:
    int numberOfBoomerangs(vector<vector<int>>& points) {
        int n = points.size(), res = 0;
        for (int i = 0; i < n; ++i) {
            map<int, int> map;
            for (int j = 0; j < n; ++j) {
                if (i == j) continue;
                int d = dis(points, i,j);
                ++map[d];
            }

            for (auto it : map) {
                res += it.second * (it.second - 1);
            }
        }
        return res;
    }

    int dis(vector<vector<int>>& points, int i, int j) {
        int x = points[i][0] - points[j][0], y = points[i][1] - points[j][1];
        return x*x + y*y;
    }
};

• Java

class Solution {
    public int numberOfBoomerangs(int[][] points) {
        int n = points.length, res = 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 dis = dis(points, i, j);
                map.put(dis, map.getOrDefault(dis, 0) + 1);
            }

            for (Map.Entry<Integer, Integer> e : map.entrySet()) {
                res += e.getValue() * (e.getValue() - 1);
            }
        }
        return res;
    }

    private int dis(int[][] points, int i, int j) {
        int x = points[i][0] - points[j][0];
        int y = points[i][1] - points[j][1];
        return x * x + y * y;
    }
}

Complexity Analysis

Time: O(n^2)

Space: O(n)

[BpointA]

思路

暴力解，哈希表记录某个点同距离的其他点，遍历得到答案。

Python3代码

class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:
        from collections import defaultdict
        dist=defaultdict(list)
        m=len(points)
        for i in range(m):
            for j in range(i+1,m):
                x1,y1=points[i]
                x2,y2=points[j]
                d=pow(x1-x2,2)+pow(y1-y2,2)
                ds=pow(d,0.5)
                dist[ds,(x1,y1)].append((x2,y2))
                dist[ds,(x2,y2)].append((x1,y1))
        ans=0
        for i in list(dist.values()):
            l=len(i)
            ans+=l*(l-1)
        return int(ans)

复杂度

时间复杂度：O(n^2)，双重遍历

空间复杂度：O(n)，哈希表长度

优化

直接记录长度，能降低空间复杂度。

class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:
        from collections import defaultdict
        dist=defaultdict(int)
        m=len(points)
        for i in range(m):
            for j in range(i+1,m):
                x1,y1=points[i]
                x2,y2=points[j]
                d=pow(x1-x2,2)+pow(y1-y2,2)
                ds=pow(d,0.5)
                dist[ds,(x1,y1)]+=1
                dist[ds,(x2,y2)]+=1
        ans=0
        for i in list(dist.values()):

            ans+=i*(i-1)
        return int(ans)      

[thinkfurther]

思路

用dict记录每一组的距离，然后对这一组排列

代码

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

        result = 0

        for i in range(n):
            temp = collections.defaultdict(int)
            for j in range(n):
                dist = (points[i][0] - points[j][0])**2 + (points[i][1] - points[j][1])**2
                temp[dist] += 1

            for val in temp.values():
                result += val*(val-1)

        return result

复杂度

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

空间复杂度：O(N)

[yachtcoder]

For every point p, use a hash map to store the distance to all other nodes pj and how many nodes are of the same distance. Each distance d, contribute k*(k-1) ways to the total count. Time: O(n^2) Space: O(n)

class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:
        def dist(p1, p2):
            return (p1[0]-p2[0])**2 + (p1[1]-p2[1])**2
        N = len(points)
        cnt = 0
        for i in range(N):
            p1 = points[i]
            d = defaultdict(int)
            for j in range(N):
                if i == j: continue
                p2 = points[j]
                d[dist(p1, p2)] += 1
            for _, v in d.items():
                cnt += v*(v-1)
        return cnt

[falconruo]

思路:

1. 使用双重循环，依次计算每一个点与其他n - 1个点之间的距离, 因为距离(distance)相同的任意三个点的tuple的顺序不同,形成的boomerang也不相同,所以对同一个distance的k个点, 从其中取出任意2个(j, k)与当前点(i)组成tuple, 排列 = k * (k - 1)
2. 在里层循环里, 计算当前点i与其n - 1个点的距离, 作为hashmap的key; 相同距离的不同点的数目作为hashmap的value
3. 在外层循环,依次计算当前点的不同距离的tuple顺序的排列数

复杂度分析:

时间复杂度: O(n^2), n为points个数 空间复杂度: O(n)

代码(C++):

class Solution {
public:
    int numberOfBoomerangs(vector<vector<int>>& points) {
        int n = points.size();

        int res = 0;
        for (int i = 0; i < n; ++i) {
            unordered_map<int, int> dist; // key: distance, value: number of points with same distance
            for (int j = 0; j < n; ++j) {
                if (i != j) {
                    int x = points[i][0] - points[j][0];
                    int y = points[i][1] - points[j][1];

                    int d2 = x * x + y * y;

                    dist[d2]++;
                }
            }

            for (auto it : dist)
                res += it.second * (it.second - 1); 
        }

        return res;
    }
};

[Menglin-l]

思路：

1.n <= 500，上brute force

2.每一次遍历都用hashmap保存距离相等的tuple，并累加满足这种条件的tuple个数

3.返回累加结果

---

代码部分：

class Solution {
    public int numberOfBoomerangs(int[][] points) {
        int ans = 0;

        for (int i = 0; i < points.length; i ++) {
            HashMap<Integer, Integer> map = new HashMap<>();
            int distance = 0;

            for (int j = 0; j < points.length; j ++) {
                if (i != j) {
                    int x = points[i][0] - points[j][0];
                    int y = points[i][1] - points[j][1];

                    distance = x * x + y * y;
                    map.put(distance, map.getOrDefault(distance, 0) + 1); // 距离，满足相等距离的个数
                }
            }

            // 要考虑顺序，用全排列
            for (int val : map.values()) {
                ans += val * (val - 1);
            }
        }

        return ans;
    }
}

---

复杂度：

Time: O(N ^ 2)

Space: O(N)

[Mahalasu]

思路

对于每一个点，计算其与其他点的距离的平方并存储到distances这个字典中，然后遍历每个平方和，得到与现在的点距离平方和相等的点的个数k，则对于该点来说回旋镖的个数就为k * (k - 1)

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

        for point in points:
            distances = {}

            for cur in points:
                h = point[0] - cur[0]
                v = point[1] - cur[1]
                square_sum = h ** 2 + v ** 2
                distances[square_sum] = 1 + distances.get(square_sum, 0)

            for i in distances:
                k = distances[i]
                ans += k * (k -1)

        return ans

T: O(N^2) S: O(N)

[harleyszhang]

解题思路

1，暴力法，时间复杂度O(n^3），最开始想到的是 3 层 for 循环迭代，但是感觉这样太复杂了，虽然以前也会用这种暴力法，但是这种常见，时间复杂度已经超过平方级了，所以写代码之前就估计会超时。

2，哈希表+排列组合思想。后面看了 leetcode官方题解（西法的题解没看明白）知道用哈希表保存和 points[i] 同样距离的点的个数，和 points[i] 距离相等的点是我们想要的，根据题目我们是要找两个点和任意的 points[i] 距离相等的三元组，即从 points 中挑 2 个点，这 2 个点和 points[i] 距离相等，因为有顺序要去，所以这2个点的挑选过程是排列过程，假设和 points[i] 距离相等的点有 n 个，那么就有n(n-1) 种情况，当然和另外两点和 points[i] 的距离是会存在多种情况的，所以这里采用了哈希表，键是任意两点和 points[i] 的距离，键值是同一个距离出现的次数。这样算能和 points[i] 组成回旋镖的情况的话，就需要计算每种距离出现的次数（次数-1），并求和。

points[i] 的情况算出来了，代码上只要第一层 for 循环 遍历 points，第二层 for 循环完成任意点和 points[i] 的距离计算，并用哈希表保存同一个距离出现的次数。然后在 for 循环遍历哈希表，计算每种距离出现的次数*（次数-1），并求和，就得到能和 points[i] 组成回旋镖的三元组个数。

（哎，感觉很难描述清楚）

class Solution {

public:
    int numberOfBoomerangs(vector<vector<int>>& points) {
        int ret = 0;
        int dist = 0;
        for(auto &p:points){
            unordered_map<int, int> count; // 创建哈希表，键值保存两点之间的距离
            for(auto &q:points){
                dist = (p[0]-q[0])*(p[0]-q[0]) + (p[1]-q[1])*(p[1]-q[1]);
                count[dist]++;
            }
            // 2个点的排列次数公式：n*(n-1)
            for(auto ct:count) ret += ct.second * (ct.second-1);
        }
        return ret;
    }
};

[pan-qin]

idea: use a HashMap to record the number of point whose distance to point[i] is equal. After finish this map, iterate through all the value in the map, if the value is n, there are n*(n-1) permutations. Then sum all the # of permutations together. Clear the map and do this for all the points on the plane. Time: O(n^2) Space: O(n)

class Solution {
    public int numberOfBoomerangs(int[][] points) {
        HashMap<Integer,Integer> distanceCounter = new HashMap<>();
        int res=0;
        for(int i=0;i<points.length;i++) {
            for(int j=0;j<points.length;j++) {
                int distance = calculateDistance(points[i],points[j]);
                distanceCounter.put(distance,distanceCounter.getOrDefault(distance,0)+1);
            }
            for(int count:distanceCounter.values()) {
                res+=count*(count-1);
            }
            distanceCounter.clear();
        }
        return res;
    }
    private int calculateDistance(int[] pointA, int[] pointB) {
        int x= pointA[0]-pointB[0];
        int y= pointA[1]-pointB[1];
        return x*x+y*y;
    }
}

[comst007]

447. 回旋镖的数量

---

思路

对于P点而言，数组中与P点距离为dist的点的个数为n, 则以P点为开头距离P点为dist的回旋镖数量为 n (n - 1)。 对于P点而言 遍历一遍原数组，统计一下 与P点距离 dist的点的数目。map[dist] = cnt。那么所以以P点开头的回旋镖的数量为:
`map[dist1] (map[dist1] - 1) + ... + map[distn] * (map[distn] - 1)` 然后对每个点都这样统计一遍就是所有回旋镖的总数。

代码

• C++

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

        int ans = 0, n;
        n = points.size();

        for(int ii = 0; ii < n; ++ ii){
            unordered_map<int, int> h_cnt;
            int x1, x2, y1, y2;
            x1 = points[ii][0];
            y1 = points[ii][1];

            for(int jj = 0; jj < n; ++ jj){
                if(jj == ii) continue;

                x2 = points[jj][0];
                y2 = points[jj][1];

                int dist = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
                h_cnt[dist] ++;  
            }
            for(auto [k, v]: h_cnt){
                ans += v * (v - 1);
            }
        }

        return ans;
    }
};

---

复杂度分析

n 为数组元素个数。

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

[florenzliu]

Explanation

• Calculate the distance between every two points
• Use a hashmap to store the count of points that have the same distance from the current point
• Since the order matters, use permutation for each count

Python

class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:
        n = len(points)
        count = 0
        for i in range(n):
            d = defaultdict(int)
            for j in range(n):
                distance = (points[i][0] - points[j][0]) ** 2 + (points[i][1] - points[j][1]) ** 2
                d[distance] += 1
            for k in d.keys():
                count += d[k] * (d[k] - 1)
        return count

Complexity

• Time Complexity: O(N²)
• Space Complexity: O(N)

[Daniel-Zheng]

思路

HashMap。

代码(C++)

class Solution {
public:
    int numberOfBoomerangs(vector<vector<int>>& points) {
        int res;
        for (int i = 0; i < points.size(); i++) {
            unordered_map<int, int> hashMap;
            for (int j = 0; j < points.size(); 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;
                hashMap[dis]++;
            }
            for (auto &it : hashMap) res += it.second * (it.second - 1);
        }
        return res;
    }
};

复杂度分析

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

[skinnyh]

Note

• For each point, use a dictionary to group other points by the distance between this point and the other point. Then for each distance group, select two other points with order to make the tuple. Get the sub result for each point as the i in the tuple and the final result is the sum of all the sub results.
• Remember to clear the dict for each point as the i point.

Solution

class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:
        d = {}
        result = 0
        for p1 in points:
            d.clear()
            for p2 in points:
                if p1 == p2:
                    continue
                dist = (p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2
                d[dist] = d.get(dist, 0) + 1
            for n in d.values():
                # From the points that have same distance of p1, select two with order
                result += n * (n - 1)
        return result

Time complexity: O(N^2)

Space complexity: O(N)

[xj-yan]

class Solution {
    public int numberOfBoomerangs(int[][] points) {
        Map<Integer, Integer> map = new HashMap<>();
        int result = 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 value : map.values()){
                result += value * (value - 1);
            }
            map.clear();
        }
        return result;
    }

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

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

[JiangyanLiNEU]

class Solution(object):
    def numberOfBoomerangs(self, points):
        D={}
        n=len(points)
        ans=0
        for i in range(n):
            for j in range(i+1,n):
                count=0
                x1,y1,x2,y2=points[i][0],points[i][1],points[j][0],points[j][1]
                dist=sqrt((x1-x2)**2+(y1-y2)**2)
                if dist in D:
                    if i in D[dist]:
                        count+=D[dist][i]
                    if j in D[dist]:
                        count+=D[dist][j]
                if dist not in D:
                    D[dist]=defaultdict(int)
                D[dist][i]+=1
                D[dist][j]+=1
                ans+=count
        return 2*ans

[yingliucreates]

link:

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

代码 Javascript

const numberOfBoomerangs = function (points) {
  let count = 0;

  for (let i = 0; i < points.length; i++) {
    const memory = {};

    for (let j = 0; j < points.length; j++) {
      if (i === j) continue;

      // search points with identical distance in memory and count tuples
      const dist =
        Math.pow(points[i][0] - points[j][0], 2) +
        Math.pow(points[i][1] - points[j][1], 2);
      if (memory[dist]) count += memory[dist] * 2;

      memory[dist] ? (memory[dist] += 1) : (memory[dist] = 1);
    }
  }

  return count;
};

复杂度分析

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

[ginnydyy]

Problem

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

Notes

• Scan all the points, calculate the distance of each point pairs, store the results into a map.
• The map key is the distance between the point[i] and point[j], the map value is the number of point[j]s that have the same distance with point[i].
• The problem is asking the number of boomerangs, so only need to store the number of points that have the same distance, do not need to store the point details.
• Iterating the map values, if there are more than two points that have the same distance of a point, then they can form a boomerang.
• According to combination knowledge, the total number of boomerangs is the combination of the number of points that have the same distance of a point. C = N * (N - 1).
• Accumulate all the combination of all the map values of all the points.
• Since -10^4 <= xi, yi <= 10^4, the square of the max distance will not exceed the int max. So can skip the Math.sqrt() for calculation in this case, and avoid using double for convenience.

Solution

class Solution {
    public int numberOfBoomerangs(int[][] points) {
        int n = points.length;
        if(points == null || n < 3){
            return 0;
        }

        int total = 0;

        for(int i = 0; i < n; i++){
            Map<Integer, Integer> distanceMap = new HashMap<>(); //Map<distance, number of points with same distance>
            for(int j = 0; j < n; j++){
                if(i != j){
                    int distance = getDistance(points, i, j);
                    distanceMap.put(distance, distanceMap.getOrDefault(distance, 0) + 1);
                }
            }

            total += countTuples(distanceMap);
        }

        return total;
    }

    private int getDistance(int[][] points, int i, int j){
        int x1 = points[i][0];
        int y1 = points[i][1];
        int x2 = points[j][0];
        int y2 = points[j][1];
        return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
    }

    private int countTuples(Map<Integer, Integer> map){
        int count = 0;
        for(int number: map.values()){
            if(number > 1){
                count += number * (number - 1);
            }
        }
        return count;
    }
}

Complexity

• Time: O(n^2) for scan the input to calculate the distance of each point pairs (n is the number of points).
• Space: O(n) for the map to store the distance results for each point. The total entries of the map is n.

[yiwchen]

思路： 扫描，哈希，数

class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:
        n = 0
        for a,b in points:
            counter = {}
            for x,y in points:
                dis = (x-a)**2 + (y-b)**2
                if dis in counter:
                    n += 2*counter[dis]
                    counter[dis] += 1
                else:
                    counter[dis] = 1
        return n

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

[zol013]

思路：nested遍历，计算每两个点的距离，将距离作为key用hashmap记录tuple of points. 然后遍历hashmap，如果每个distance里有两个或以上的点tuple， 用set()查看是否有共同点。如果有共同点， 则说明有两个回旋镖（因为考虑点的排序，每找到符合条件的三个点，则有两个回旋镖） Python 3 Code:

class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:
        ans = 0
        hashmap = defaultdict(list)
        for i in range(len(points)):
            for j in range(i + 1, len(points)):
                dist = (points[i][0] - points[j][0])**2 + (points[i][1]-points[j][1])**2
                hashmap[dist].append((tuple(points[i]), tuple(points[j])))
        for dist in hashmap.keys():
            if len(hashmap[dist]) > 1:
                for i in range(len(hashmap[dist])):
                    for j in range(i+1, len(hashmap[dist])):
                        if len(set(hashmap[dist][i] + hashmap[dist][j])) == 3:
                            ans += 2
        return ans

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

[RocJeMaintiendrai]

题目

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

思路

使用HashMap，以a开头的回旋镖满足 distance(a,b) = distance(a,c)那么我们遍历一遍数组points,找到a和其它元素的距离dis和出现的次数cnt，并记录下来。

代码

class Solution {
    public int numberOfBoomerangs(int[][] points) {
        Map<Integer, Integer> map = new HashMap<>();
        int boomerangs = 0;
        for(int i = 0; i < points.length; i++) {
            for(int j = 0; j < points.length; j++) {
                if(i == j) {
                    continue;
                }
                int distance = (points[i][0] - points[j][0]) * (points[i][0] - points[j][0]) + (points[i][1] - points[j][1]) * (points[i][1] - points[j][1]);
                map.put(distance, map.getOrDefault(distance, 0) + 1);
            }
            for(Integer distance : map.values()) {
                boomerangs += distance * (distance - 1);
            }
            map.clear();
        }
        return boomerangs;
    }
}

复杂度分析

时间复杂度

O(n^2)

空间复杂度

O(n)

[nonevsnull]

思路

• 拿到题的直觉解法
  • 对每个点，要用hashmap存储计算的距离，如果有相同的就形成一个集合，然后排列组合计算有多少个pair；

需要注意的问题：不要过早优化 花了不少时间去想怎么优化。真正面试时，最好是先按照简单的思路写出来，再边沟通，边优化； 想太多优化，会容易钻进去，缺乏沟通，而且最后可能会卡住，影响思路；

AC

代码

class Solution {
    public int numberOfBoomerangs(int[][] points) {
        if(points.length < 3) return 0;
        int res = 0;
        for(int i = 0;i < points.length;i++){
            int[] sp = points[i];
            HashMap<Long, Integer> distanceToPoint = new HashMap<>();
            for(int j = 0;j < points.length;j++){
                if(i == j) continue;
                long dis = (sp[0] - points[j][0])*(sp[0] - points[j][0]) + (sp[1] - points[j][1])*(sp[1] - points[j][1]);
                if(distanceToPoint.containsKey(dis)){
                    distanceToPoint.put(dis, distanceToPoint.get(dis)+1);
                }else{
                    distanceToPoint.put(dis, 1);
                }

            }
            for(long dis: distanceToPoint.keySet()){
                int k = distanceToPoint.get(dis);
                res += k*(k-1);
            }
        }
        return res;
    }
}

复杂度

time: 每个点都遍历了所有其他点，O(N^2) space: 需要一个hashmap存储，O(N)

[Yufanzh]

Intuition

The problem ask to output number of Booerangs, which is equal to find (j,k) that has the same distance to i. This can be recorded by a hashmap with key = two points' distance, val = number of points that has the distance to i. Then we loop through keys in map and added the permutations of those numbers in each key.

Algorithm in python3

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

        for i in range(n):
            distMap = {}
            for j in range(n):
                if i == j:
                    continue
                x = points[j][0] - points[i][0]
                y = points[j][1] - points[i][1]
                dist = x*x + y*y
                if dist in distMap:
                    distMap[dist] += 1
                else:
                    distMap[dist] = 1

            for key in distMap:
                ans += distMap[key] * (distMap[key]-1)
        return ans

Complexity Analysis

• Time complexity: O(n^2)
• Space complexity: O(n)

[wangzehan123]

class Solution {
    public int numberOfBoomerangs(int[][] points) {
    //Hashmap<欧式距离，次数>
        Map<Double,Integer> map = new HashMap<>();
        int len = points.length;
        int res = 0;
    //两层循环遍历所有元素
        for(int i = 0;i < len;i ++){
            for(int j = 0;j < len;j ++){
        //求出欧式距离
                double distance = Math.pow(points[i][0] - points[j][0],2) + Math.pow(points[i][1] - points[j][1],2);
        //如果存在这个距离的元素，则先运算存入res中，并令其次数+1
                if(map.containsKey(distance)){
                    int val = map.get(distance);
                    res += 2 * val;
                    map.put(distance,val + 1);
                }else{
            //否则存入，令其次数为1
                    map.put(distance,1);
                }
            }
       //本次循环结束，清空map
            map.clear();
        }
        return res;
    }
}

复杂度分析

令 n 为数组长度。

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

[pophy]

思路

• 遍历Points， 计算其他Point到当前point的距离 并按距离为key放到map中
  • Map的结构为 Map<point, Map<distance, count>>
• 遍历map中的值 计算结果

Java Code

class Solution {
    public int numberOfBoomerangs(int[][] points) {
        if (points == null || points.length == 0) {
            return 0;
        }
        int n = points.length;
        Map<int[], Map<Integer, Integer>> countMap = new HashMap<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) {
                    continue;
                }
                if (countMap.get(points[i]) == null) {
                    countMap.put(points[i], new HashMap<>());
                }
                Map<Integer, Integer> distMap = countMap.get(points[i]);
                int dist = getDistance(points[i], points[j]);
                distMap.put(dist, distMap.getOrDefault(dist, 0) + 1);
            }
        }
        int count = 0;
        for (int[] point : countMap.keySet()) {
            Map<Integer, Integer> distMap = countMap.get(point);
            for (int dist : distMap.keySet()) {
                count += distMap.get(dist) * (distMap.get(dist) - 1);
            }
        }
        return count;
    }

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

时间 & 空间

• 时间 O(n^2)
• 空间 o(n)

[erik7777777]

思路

找等腰三角形， 开始的时候想过排序，可行是可行，但是排序方式比较傻，拿出当前点，假设为顶点，对剩下的点用到顶点距离排序，双指针可以扫（不确定是否可行） 那么直接就暴力扫也行，不存在重复点的情况下，比较好写，两层循环，map里面存边长，当边长大于一条的时候，意味着新加进去的边可以和之前的所有边组成2 * 边数个回旋镖

代码

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

    private int calculate(int[] a, int[] b) {
        return (a[0] - b[0]) * (a[0] - b[0]) + (a[1] - b[1]) * (a[1] - b[1]);
    }
}

复杂度分析

time : O(n ^ 2) space : O(n) size of map

[akxuan]

思路

枚举就是 N^2, 字典用的有点浪费

O(N^2)

class Solution(object):
    def numberOfBoomerangs(self, points):
        """
        :type points: List[List[int]]
        :rtype: int
        """

        dis_hash = {}

        def cal_dis(p,q):
            x1,y1 = p
            x2,y2 = q
            return (x1-x2)**2 + (y1-y2)**2

        for index,r in enumerate( points):
            temp_hash = {}
            keep = False
            for c in points:
                if r!= c :
                    if cal_dis(r,c) in temp_hash:
                        temp_hash[cal_dis(r,c)] += [c]    
                        keep = True
                    else:
                        temp_hash[cal_dis(r,c)] = [c]
            if keep :
                dis_hash[index] = temp_hash

        res = 0
        print( dis_hash)
        for key, value in dis_hash.items():
            for i, v in value.items():
                if len(v) >1:
                    res += len(v)*( len(v) - 1)

        return res

[heyqz]

代码

class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:
        res = 0
        for x1, y1 in points:
            dicts = {}
            for x2, y2 in points:
                if x1 == x2 and y1 == y2:
                    continue
                dx = x1 - x2
                dy = y1 - y2
                dsquare = (dx*dx) + (dy*dy)
                dicts[dsquare] = 1 + dicts.get(dsquare, 0)

            for key in dicts:
                res += dicts[key] * (dicts[key] - 1)

        return res

复杂度

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

[tongxw]

思路

对每个点i，计算其他点到它的距离。以点i为起点的回旋镖个数是到它相同距离的点的排列数Pn取2 用哈希表实现相同距离的计数操作 最后把所有的回旋镖个数加起来即可。

代码

var numberOfBoomerangs = function(points) {
    let ans = 0;
    for (let i=0; i<points.length; i++) {
      const distMap = new Map();
      for (let j=0; j<points.length; j++) {
        if (i == j) {
          continue;
        }
        const dist = Math.pow(points[i][0] - points[j][0], 2) +  Math.pow(points[i][1] - points[j][1], 2);
        const count = distMap.get(dist) || 0;
        distMap.set(dist, count + 1);
      }

      for (const entry of distMap) {
        ans += entry[1] * (entry[1] - 1);
      }
    }

    return ans;
};

• TC: O(n2)
• SC: O(n)

[zhangzz2015]

思路

• 对于每个点，找到distance相同的点数n 。则形成回旋镖从相同的点数取两个点的组合数为Cn^2= n*(n-1)。时间复杂度为O(N^2)，空间复杂度为 O(N)，利用hash map 来记录其他点到当前点的相同distance的个数。

关键点

代码

• 语言支持：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> recordDistance;             
            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]) ;

                recordDistance[dis]++;
            }
            for(unordered_map<int, int>::iterator it2 = recordDistance.begin(); it2!=recordDistance.end(); it2++)
            {
                  ret += (*it2).second * ( (*it2).second-1 ) ; 
            }
        }

        return ret; 
    }
};

[mmboxmm]

思路

数学题

代码

fun numberOfBoomerangs(points: Array<IntArray>): Int {
  if (points.size <= 2) return 0
  val map = mutableMapOf<Int, Int>()
  var res = 0
  for (first in points) {
    map.clear()
    for (second in points) {
      val dis =
        (first[0] - second[0]) * (first[0] - second[0]) + (first[1] - second[1]) * (first[1] - second[1])
      map[dis] = map.getOrDefault(dis, 0) + 1
    }
    res += map.values.fold(0) { acc, i -> acc + i * (i - 1) }
  }
  return res
}

[chenming-cao]

解题思路

哈希表。双层循环遍历数组，第一层循环选取中心点，第二层循环计算每个点到中心点距离，再将每个距离出现的次数存入哈希表，最后用排列公式计算可能出现回旋镖数。

代码

class Solution {
    public int numberOfBoomerangs(int[][] points) {
        int num = 0;
        Map<Double, Integer> map = new HashMap<>();
        for (int i = 0; i < points.length; i++) {
            int[] base = points[i];
            for (int j = 0; j < points.length; j++) {
                int[] cur = points[j];
                double d = Math.pow(cur[0] - base[0], 2.0) + Math.pow(cur[1] - base[1], 2.0);
                map.put(d, map.getOrDefault(d, 0) + 1);
            }
            for (double d: map.keySet()) {
                int count = map.get(d);
                num += count * (count - 1);
            }
            map.clear();
        }
        return num;
    }
}

复杂度分析

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

[hwpanda]

var numberOfBoomerangs = function(points) {
  const n = points.length;

  const dists = [];

  for (let i = 0; i < n; i++) {
      const map = new Map();
      const [x1, y1] = points[i];

      for (let j = 0; j < n; j++) {
          if (i === j) continue;

          const [x2, y2] = points[j];

          const dist = Math.sqrt((x1 - x2)**2 + (y1 - y2)**2);

          if (!map.has(dist)) map.set(dist, 0);
          map.set(dist, map.get(dist) + 1);
      } 

      dists[i] = map;
  }

  let res = 0;

  for (let i = 0; i < n; i++) {
      const map = dists[i];

      for (const count of map.values()) {
          res += (count * (count - 1));
      }
  }

  return res;
};

[biancaone]

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

        result = 0

        for point in points:
            mapping = {}
            for p in points:
                x = p[0] - point[0]
                y = p[1] - point[1]
                distance = x * x + y * y
                mapping[distance] = mapping.get(distance, 0) + 1

            for distance in mapping:
                result += mapping[distance] * (mapping[distance] - 1)

        return result

[joeytor]

思路

遍历所有points, 然后遍历所有其他的points, 计算距离, 每次把距离的count加到哈希表中, 遍历完所有points之后

遍历所有dict的values, 然后将 k * (k-1) 加入 count 中

最后返回 count

代码

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

        res = 0

        for i, p1 in enumerate(points):
            d = collections.defaultdict(int)
            for j, p2 in enumerate(points):
                if i != j:
                    dist = (p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2
                    d[dist] += 1
            for dis, count in d.items():
                res += count * (count - 1)

        return res

复杂度

N 为 points 的长度

时间复杂度: O(N^2) 两重循环遍历 points 数组

空间复杂度: O(N) 哈希表 d 的最差空间复杂度为 O(N) 即数组的长度

[suukii]

Link to LeetCode Problem

S1: 枚举+哈希表计数

根据题意，回旋镖是指：

坐标上有三个点 i, j, k，i 到 j 的距离等于 i 到 k 的距离。上图中，蓝色的点到两个橙色的点距离是一样的，所以 (i, j, k) 构成了一个回旋镖，同时 (i, k, j) 也构成了一个回旋镖。

其实可以想到，对于每个点：

1. 只需要将其他点按照与该点的距离进行分组，比如上图中的 [1, 1]，距离它 $\sqrt[]{2}$ 的点有 [0, 0] 和 [2, 0]。
2. 然后再计算排列组合数，也就是对 $\sqrt[]{2}$ 这个距离分组中的点进行两两排列组合，就可以得出答案了。

第一步的分组如果使用哈希表来记录的话，它的结构大概是这样的：

{
    point1: {
        dist1: [point2, point3],
        dist2: [point4]
    },
    point2: {...},
}

每个点都维护一个哈希表，哈希表的键是该点到其他点的距离，值就是在这个距离的点有哪些。

不过题目只要求输出回旋镖的数量，所以我们可以只记录在某个距离的点有几个，并不需要记录具体的坐标，比如 dist1: 2 就可以了。

计算两点距离公式：$\sqrt[2]{(x1-x2)^2+(y1-y2)^2}$ ，不过其实我们只关心距离是否一样，并不关心实际距离是多少，所以实际上不需要开根号。

两两组合数：一个集合中有 N 个数，每个数都可以跟其余 N-1 个数进行组合，一共有 $N*(N-1)$ 种组合。

class Solution {
public:
    int numberOfBoomerangs(vector<vector<int>>& points) {
        int count = 0;
        for (const auto& a : points) {
            unordered_map<int, int> distMap;
            for (const auto& b : points) {
                int dist = pow(a[0] - b[0], 2) + pow(a[1] - b[1], 2);
                distMap[dist]++;
            }
            for (const auto& [_, d] : distMap) {
                count += d * (d - 1);
            }
        }
        return count;
    }
};

/**
 * @param {number[][]} points
 * @return {number}
 */
var numberOfBoomerangs = function (points) {
    let count = 0;

    points.forEach((a, i) => {
        const map = {};

        points.forEach((b, j) => {
            if (a !== b) {
                const dist = calcDistOf2Points(a, b);
                map[dist] = (map[dist] || 0) + 1;
            }
        });

        for (const dist in map) {
            const num = map[dist];
            if (num > 1) count += num * (num - 1);
        }
    });

    return count;

    // ******************************
    function calcDistOf2Points([x1, y1], [x2, y2]) {
        return (x1 - x2) ** 2 + (y1 - y2) ** 2;
    }
};

• Time: $O(N^2)$，N 是数组长度。一共有两层循环，在内层循环中，寻找某点到所有其他点的距离时间是 $O(N)$，计算组合数的时间是 $O(m)$，m 是每个点到其他点的不同距离总数的最大值，m 最大值是 N-1。所以总的时间是 $O(N*(N+m))$，差不多是 $O(N^2)$。
• Space: $O(N)$，最坏的情况是每个点到其他点的距离都不一样，那每个哈希表的大小就是 N-1。

[kidexp]

thoughts

先遍历数组得到两两之间的distance 分别存把每个distance 存到对应的哈希表中，计算有这个distance的有多少个

然后枚举所有的点和distance，如果这个点可以和这个distance组成一个回旋镖，那么会有对应和这个点组成distance的长度的点有至少2个（假设k个） 用排列的知识得出有k(k-1)个 所有加起来就是回旋镖的数目

code

from collections import defaultdict

class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:
        n = len(points)
        point_distance_dict = {i: defaultdict(int) for i in range(n)}
        for i in range(n):
            for j in range(i + 1, n):
                distance = (points[i][0] - points[j][0]) ** 2 + (
                    points[i][1] - points[j][1]
                ) ** 2
                point_distance_dict[i][distance] += 1
                point_distance_dict[j][distance] += 1
        result = 0
        for i in range(n):
            for distance in point_distance_dict[i]:
                if point_distance_dict[i][distance] > 1:
                    result += point_distance_dict[i][distance] * (
                        point_distance_dict[i][distance] - 1
                    )
        return result

complexity

time O(n^2)

space O(n^2)

[LAGRANGIST]

class Solution { public: int numberOfBoomerangs(vector<vector> &points) { int ans = 0; for (auto &p : points) { unorderedmap<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; } };

[wangyifan2018]

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

[shawncvv]

思路

官方解题思路

代码

Python Code

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)

[JinMing-Gu]

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;
    }
};

[chakochako]

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

        for x1, y1 in points:
            cnt = Counter()
            for x2, y2 in points:
                k = (x1 - x2) ** 2 + (y1 - y2) **2
                cnt[k] += 1
            for k, v in cnt.items():
                if v > 1:
                    ans += v * (v - 1)
        return ans

[user1689]

题目

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

思路

哈希表+排列数

python3

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

        # time n**2
        # space 1
        # 思路一
        # 枚举 + 哈希表

        ans = 0
        for p in points:
            dic = defaultdict(int)
            for q in points:
                dis = (q[0] - p[0]) * (q[0] - p[0]) + (q[1] - p[1]) * (q[1] - p[1])
                # {char:frequency}
                dic[dis] += 1
            for value in dic.values():
                # 大于1就求排列数并累加答案
                if value > 1:
                    # 排列:第一个空位有n个可以选，第二个空位有(n - 1)个可以选
                    # 即n * (n - 1)
                    ans += value * (value - 1)
            # print(dic)
        return ans

复杂度分析

• time n**2
• space n

相关题目

1. https://leetcode-cn.com/problems/line-reflection/

[Francis-xsc]

思路

以每个点为中间点遍历 用哈希表记录到每个点距离出现的次数 以当前为中间点的回旋镖数量为x*(x-1)

代码

class Solution {
public:
    int numberOfBoomerangs(vector<vector<int>>& points) {
        int len=points.size(),res=0;
        for(int i=0;i<len;++i)
        {
            unordered_map<int,int> m; 
            for(int j=0;j<len;j++)
            {
                int x=(points[i][0]-points[j][0]);
                int y=(points[i][1]-points[j][1]);
                m[x*x+y*y]++;
            }
            for(auto x:m)
            {
                res+=x.second*(x.second-1);
            }
        }
        return res;
    }
};

复杂度分析

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

[watermelonDrip]

class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:
        def distance(x,y):
            return (x[0] - y[0])**2 + (x[1] - y[1])**2
        def permutaion(n):
            return n*(n-1)

        res = 0

        for i in range(len(points)):
            dict_p = dict()
            for j in range(len(points)):
                tmp = distance(points[i],points[j])

                dict_p[tmp] = dict_p.get(tmp,0) + 1
            for t in dict_p.values():
                if t > 1:
                    res += permutaion(t)
        return res

time complexity: O(n**2) space: O(n)

1. for each point i, find the square distance 'distance(p[i], p[j])' for other points j
2. count all points with same distance
3. apply permutation function to get boomerangs
4. add theses to the final res

[st2yang]

思路

• dict; math

代码

• python

  class Solution:
  def numberOfBoomerangs(self, points: List[List[int]]) -> int:
      res = 0
      for p in points:
          cnt = defaultdict(int)
          for q in points:
              dis = (p[0] - q[0]) * (p[0] - q[0]) + (p[1] - q[1]) * (p[1] - q[1])
              cnt[dis] += 1
          for m in cnt.values():
              res += m * (m - 1)  # m个元素中选两个
      return res

复杂度

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

[Cartie-ZhouMo]

思路

对每个点计算其余点与它的距离存储在哈希表中，利用排列计算组成回旋镖的数量。

代码

class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:
        def dis(x, y):
            return pow(x[0] - y[0], 2) + pow(x[1] - y[1], 2)
        m = len(points)
        ans = 0
        for i in range(m):
            dic = {}
            for j in range(m):
                d = dis(points[i], points[j])
                dic[d] = dic.setdefault(d, 0) + 1
            for x in dic:
                ans += dic[x] * (dic[x] - 1)
        return ans

复杂度

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

[wenlong201807]

解题思路

1. 遍历points，将每个点作为顶点，计算其他点到顶点的距离，保存相同距离点的数量在map中
2. 遍历每个map，若与顶点相同距离的点的个数大于1，则计算组成回旋镖的数量
3. 一共num，其中挑2个出来，有num*(num-1)个可能

代码块

// 计算两点距离的平方
const getD = ([a1, a2], [b1, b2]) => (b1 - a1) ** 2 + (b2 - a2) ** 2;

const numberOfBoomerangs = points => {
    // 肯定组成不了回旋镖
    if (points.length < 3) return 0;

    const map = {};
    let res = 0;

    points.forEach((a, i) => {
        // 遍历时，将每个点作为顶点
        map[a] = {};
        // 再次遍历，得到其余的点到顶点的距离
        points.forEach((b, j) => {
            // 排除与自身的点
            if (i !== j) {
                // 计算距离
                const d = getD(a, b);
                // 将距离保存
                map[a][d] = (map[a][d] || 0) + 1;
            }
        });
        // 遍历顶点map
        for (const item in map[a]) {
            // 与顶点相同距离的点的个数
            const num = map[a][item];
            // num>1，才能和顶点组成回旋镖
            // 一共num，其中挑2个出来，有num*(num-1)个可能
            if (num > 1) res += num * (num - 1);
        }
    });

    return res;
};

时间复杂度和空间复杂度

• 时间复杂度 O(n)
• 空间复杂度 O(1)

[shixinlovey1314]

Title:447. Number of Boomerangs

Question Reference LeetCode

Solution

Assign each point a bucket, inside the bucket is a hashmap used to store the distance to other points and the number of points that has the same distance. Calculate the distance of any two points, and update the hashmap in each bucket, update the final number along the way.

Let's say for point x, there exist one point which distance to x is a --- [a, 1] Now when we encounter another point that has the same distance, we now have a pair of points that has the same distance to x. -- [a, 2] Since the order matters we actually have (2 * pair) of new boomerangs.

When we encoutner another point, since we already have 2 points, adding a new point would result 2 new pairs. . . . When we already have n points, adding a new point to the set would reasult in n new pairs, which is (2 * n) new boomerangs.

Code

    int numberOfBoomerangs(vector<vector<int>>& points) {
        int ans = 0;
        vector<map<double,int>> counter(points.size());
        for (int i = 0; i < points.size() - 1; i++) {
            for (int j = i + 1; j < points.size(); j++) {
                double dis = sqrt(pow((points[i][0] - points[j][0]), 2)+pow((points[i][1] - points[j][1]), 2));
                // Gradually add the number of Boomerangs. 
                ans += 2 * (counter[i][dis]++) + 2 * (counter[j][dis]++);
            }
        }

Complexity

Time Complexity and Explanation

O(n^2)

Space Complexity and Explanation

O(n^2)

[BlueRui]

Problem 447. Number of Boomerangs

Algorithm

• The problem is to find all the tuple of points (A, B, C) such that A has equal distance to B and C. (A, B, C) and (A, C, B) are two different tuples.
• We can use two layers of for loops. In the first layer, let every point points[i] be A. In the second layer, get the distance from A to all other points points[j] and save it to a map whose key is distance and value is the count of this distance.
• In each iteration of first layer of loop, we calculate the number of tuples with points[i] being A summing up all the permutations of the same distance in the map.
• The key is to clear the map at the end of each iteration of the first layer.

Complexity

• Time Complexity: O(N²) for two layers of for loop.
• Space Complexity: O(N) for the map.

Code

Language: Java

public int numberOfBoomerangs(int[][] points) {
    if (points.length < 3) {
        return 0;
    }
    int result = 0;
    Map<Integer, Integer> distances = new HashMap<>();
    for (int i = 0; i < points.length; i++) {
        for (int j = 0; j < points.length; j++) {
            if (i == j) {
                continue;
            }
            int distance = (int) (Math.pow(points[i][0] - points[j][0], 2) + Math.pow(points[i][1] - points[j][1], 2));
            distances.put(distance, distances.getOrDefault(distance, 0) + 1);
        }
        for (Integer count : distances.values()) {
            result += count * (count - 1);
        }
        distances.clear();
    }
    return result;
}