【Day 21 】2022-04-21 - 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]]

[rzhao010]

Thoughts Treat each point as the mid point, and calculate the distance between current point with all other points. Mapping the distance and the counts. Then traverse the keySet of map to get the total count of different pairs(EACH TIME WE SELECT TWO, so it's A(N, 2) = n * (n - 1))

Code

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 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 ^ 2) Space: O(n)

[MichaelXi3]

Idea

• Iterate through all points and calculate all Euclidean distances about that point, then store the distances with their frequency into HashMap.

• Calculate the combinations for all possible Boomerangs, "distFreq C 2", then sum them and return.

  Code

  class Solution {
  public int numberOfBoomerangs(int[][] points) {
      int result = 0;
      // Empty input 
      if (points == null || points.length <= 2) {
          return 0;
      }
      // Create HashMap to store 
      Map<Integer, Integer> count = new HashMap<>();
  
      // Iterate through all points, find and count the # of repeated distances
      for (int i=0; i<points.length; i++) {
          for (int j=0; j<points.length; j++) {
              int distance = getDistance(points[i], points[j]);
              count.put(distance, count.getOrDefault(distance, 0) + 1);
          }
  
          for (int countNum : count.values()) {
              result += countNum*(countNum-1);
          }
          count.clear();
      }
  
      return result;
  }
  
  public int getDistance (int[] a, int[] b) {
      int xdiff = a[0] - b[0];
      int ydiff = a[1] - b[1];
      int distance = 0;
      distance = xdiff * xdiff + ydiff * ydiff;
      return distance;
  }
  }

  Time & Space Complexity

• Time Complexity: O(n^2) // n is the number of points
• Space Complexity: O(n) // HashMap memory space

[forestie9]

Ideas

Use hashmap, count the matched one twice

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

    for x1, y1 in points:
      count = collections.defaultdict(int)
      for x2, y2 in points:
        ans += 2 * count[(x1 - x2)**2 + (y1 - y2)**2]
        count[(x1 - x2)**2 + (y1 - y2)**2] += 1

    return ans

complexity

Time O(n^2), space O(n)

[HuiWang1020]

Idea

1. calculate distance. for each point i, calculate the distance from i to j (all points except itself).
2. get same distance using hashmap. key: the position of current point. value: distance
3. get all possible combinations. order matters.

   Code

   class Solution {
   public int numberOfBoomerangs(int[][] points) {
       if(points == null || points.length < 3)return 0;
       int res = 0;
       for(int i = 0; i < points.length; i++) {
          Map<Integer, Integer> map = new HashMap<>();
          for(int j = 0; j < points.length; 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(int key : map.keySet()) {
               int fre = map.get(key);
               res += fre * (fre - 1);
           } 
      }
    return res;   
   }
   }

   Complexity

   time=O(N^2) space=O(N)

[ZacheryCao]

Idea

Hashmap

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

Complexity:

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

[xixiao51]

Idea

For each point i, map<distance d, count of all points at distance d from i>. Given that count, choose 2 (with permutation) from it, to form a boomerang with point i.

Code

class Solution {
    public int numberOfBoomerangs(int[][] points) {
        int res = 0;
        for(int i = 0; i < points.length; i++) {
            Map<Integer, Integer> map = new HashMap<>();
            for(int j = 0; j < points.length; 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 num : map.values()) {
                /*
                 * for all the groups of points, 
                 * number of ways to select 2 from n = 
                 * nP2 = n!/(n - 2)! = n * (n - 1)
                 */
                res += num * (num - 1);
            }
        }

        return res;
    }
}

Complexity Analysis

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

[kite-fly6618]

思路：

map 保存每个拐点到其他节点的距离相等的个数，统计当前节点构成回旋镖的数量

代码：

var numberOfBoomerangs = function(points) {
    let ans = 0;
    for (const p of points) {
        const cnt = new Map();
        for (const q of points) {
          // 距离为0的点有一个，m*(m-1) 后就会变成0,不影响
          const dis = (p[0] - q[0]) * (p[0] - q[0]) + (p[1] - q[1]) * (p[1] - q[1]); 
          cnt.set(dis, (cnt.get(dis) || 0) + 1);
        }
        // 计算以这个点为拐点的回旋镖数量，在m中取两个的排列组合 m*（m-1）
        for (const [_, m] of cnt.entries()) {
          ans += m * (m - 1);
        }
        // console.log(cnt.entries())
    }

    return ans;
};

复杂度：

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

[oneline-wsq]

思路

哈希表

代码

class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:
        ans=0
        for p in points:
            cnt=defaultdict(int)
            # defaultdict的作用是在于，当字典里的key不存在但被查找时，返回的不是keyError而是一个默认值. int时，默认是0
            for q in points:
                dis=(p[0]-q[0])**2+(p[1]-q[1])**2
                cnt[dis]+=1 # 这里将距离数存在字典里
            for m in cnt.values():
                ans+=m*(m-1)
        return ans

复杂度分析

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

空间复杂度：O(n)

[ShawYuan97]

思路

采用双重循环，第一重循环确定一个点p_i 第二重循环确定第二个点p_j，计算两个点之间的距离dist，将dist作为key，dist数量为value，那么回旋镖数量为value * (value-1)

关键点

• 哈希表

代码

• 语言支持：Python3

Python3 Code:

class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:
        """
        计算回旋镖的数量
        回旋镖定义：元组(i,j,k)，其中点i与点j和点k的距离相等（需要考虑元组顺序）
        """
        # 边界判断
        if len(points) < 3:
            return 0
        ans = 0 
        for i in range(len(points)):
            dist_map = collections.defaultdict(int)
            for j in range(len(points)):
                dx = points[i][0]-points[j][0]
                dy = points[i][1]-points[j][1]
                dist = dx*dx + dy*dy
                dist_map[dist] += 1
            for val in dist_map.values():
                ans += val * (val-1)
        return ans 

复杂度分析

令 n 为数组长度。

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

[YuyingLiu2021]

class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:
        #把每一个点作为一个中点，分别计算别的点和这个点的距离，如果距离都相等的话 就是一个回旋镖
        #写一个dist的helper function 然后直接算
        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()
            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

[houmk1212]

思路

暴力枚举的方法。遍历点，以点作为中间点i。 并通过哈希表存储所有其他点到当前点的不同距离的点有多少个。根据排列原理，就可以通过遍历哈希表计算出能够得到回旋镖的数量。

代码

class Solution {
    public int numberOfBoomerangs(int[][] points) {
        int res = 0;
        for (int[] p : points) {
            HashMap<Integer, Integer> map = new HashMap<>();
            map.clear();
            for (int[] q : points) {
                int dis = (p[0] - q[0]) * (p[0] - q[0]) + (p[1] - q[1]) * (p[1] - q[1]);
                if (dis != 0) {
                    map.put(dis, map.getOrDefault(dis, 0) + 1);
                }
            }

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

复杂度

• 时间复杂度：O（N2）
• 空间复杂度：O（N）

[TimmmYang]

思路

枚举+哈希统计每个点到剩余点的距离频次。最后对于freq频次大于等于2时就满足条件。结果为$2C_{freq}^2$，即freq * (freq - 1).

代码

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

        res = 0
        for point1 in points:
            d = []
            for point2 in points:
                d.append(distance(point1, point2))
            count = Counter(d)
            for dist, freq in count.items():
                if freq > 1:
                    res += freq * (freq - 1)
        return res 

复杂度

时间复杂度：O(n^2)，n为points个数

空间复杂度：O(n)

[KelvinG-LGTM]

思路

暴力枚举

代码

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

复杂度分析

时间复杂度

O(N^2)

空间复杂度

O(N)

[Magua-hub]

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

        int res = 0;
        for (int i = 0; i < p.size(); i ++ ) {
            unordered_map<int, int> cnt;
            for (int j = 0; j < p.size(); j ++ )
                if (i != j) {
                    int dx = p[i][0] - p[j][0];
                    int dy = p[i][1] - p[j][1];
                    int dist = dx * dx + dy * dy;
                    cnt[dist] ++ ;
                }
            for (auto [d, c]: cnt) res += c * (c - 1);
        }
        return res;
    }
};

[1973719588]

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

        sum = 0
        for i in range(len(points)):
            dic = {}
            for j in range(len(points)):
                if i != j:
                    a, b = points[i]
                    x, y = points[j]
                    le = np.sqrt(abs(a-x)**2 + abs(b-y)**2)
                    if le not in dic:
                        dic[le] = 1
                    else:
                        dic[le] += 1
            for x in dic:
                y = dic[x]
                sum = sum + y * (y-1)

        return sum

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

[TonyLee017]

思路

哈希表+穷举

代码

class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:
        res = 0
        for p in points:
            count = defaultdict(int)
            for q in points:
                dis = (p[0] - q[0])**2 + (p[1] - q[1])**2
                count[dis] += 1
            for m in count.values():
                res += m*(m-1)
        return res

复杂度分析

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

[hyh331]

Day21 思路

哈希+排列数(是有顺序的考虑用A)

1. 对每一个回旋镖中心i，先计算该点与其他点的距离，并以距离为键值通过哈希表记录这些点的数量，即哈希表key值为距离，value值相同距离下出现点的次数

2. 计算完所有数组后，遍历哈希表，对每种距离下可以构造的回旋镖的数量num*(num-1)求和即可

   class Solution {
   public:
   int numberOfBoomerangs(vector<vector<int>>& points) {
       int ans = 0;
       //遍历每个点
        unordered_map<int, int> m;
       for (int i = 0; i < points.size(); i ++) {
   
           //遍历其他点
           for (int j = 0; j < points.size(); j ++) {
               //若是同一个点则开始下一轮循环，continue跳过当前循环中的代码，强迫开始下一次循环
               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;
               //将距离作为key值放入unordered_map容器中，
               m[dis] ++;
           }
           //遍历m容器，将每个key值对应的可组合回旋镖的数量求出，并求和
           for(auto &[key, num]: m){
               ans += num * (num - 1);
           }
       }
       return ans;
   }
   };

   复杂度分析

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

[zjsuper]

class Solution: def numberOfBoomerangs(self, points: List[List[int]]) -> int: def dis(a,b): return (a[0]-b[0])2 +(a[1]-b[1])2

collections.defaultdict(int)

    dic = [{} for _ in range(len(points))]
    for i in range(len(points)):
        for j in range(len(points)):
            if i!= j:
                dist = dis(points[i],points[j])
                if dist not in dic[i]:
                    dic[i][dist] = 1
                else:
                    dic[i][dist] +=1
    ans = 0   
    #print(dic)
    for d in dic:
        for k,v in d.items():
            if v >1:
                #print(2*math.comb(v,2))
                ans += 2*math.comb(v,2)

    return ans

[dzwhh]

【Day 21】447.Number of Boomerangs「回旋镖的数量」

• 题目地址: https://leetcode-cn.com/problems/number-of-boomerangs/

题目描述

给定平面上 n 对 互不相同 的点 points ，其中 points[i] = [xi, yi] 。回旋镖 是由点 (i, j, k) 表示的元组 ，其中i 和 j 之间的距离和 i 和 k 之间的欧式距离相等（需要考虑元组的顺序）。 返回平面上所有回旋镖的数量。

示例 1

输入：points = [[0,0],[1,0],[2,0]] 输出：2 解释：两个回旋镖为 [[1,0],[0,0],[2,0]] 和 [[1,0],[2,0],[0,0]]

示例 2

输入：points = [[1,1],[2,2],[3,3]] 输出：2

示例 3

输入：points = [[1,1]] 输出：0

前置知识

• 哈希表

思路

我们可以遍历 points，计算并统计所有点到 points[i] 的距离，将每个距离的出现次数记录在哈希表中，然后遍历哈希表，并用上述公式计算并累加回旋镖的个数。

代码

• js 版本

const numberOfBoomerangs = points => {
    let ans = 0;
    for (const p of points) {
        const cnt = new Map();
        for (const q of points) {
            const dis = (p[0] - q[0]) * (p[0] - q[0]) + (p[1] - q[1]) * (p[1] - q[1]);
            cnt.set(dis, (cnt.get(dis) || 0) + 1);
        }
        for (const [_, m] of cnt.entries()) {
            ans += m * (m - 1);
        }
    }
    return ans;
};

复杂度分析

时间复杂度:O(n2) 空间复杂度:O(n)

[LyuliangLiu]

Idea

For every point, have a map<Distance, Count>. Count -> A(Count, 2) = count * (count - 1).

Code

class Solution {
    public int numberOfBoomerangs(int[][] points) {
        int result = 0;
        for (int i = 0; i < points.length; i++) {
            Map<Integer, Integer> distToCount = new HashMap<>();
            for (int j = 0; j < points.length; j++) {
                int xDiff = points[i][0] - points[j][0];
                int yDiff = points[i][1] - points[j][1];
                int dist = xDiff * xDiff + yDiff * yDiff;
                int count = distToCount.getOrDefault(dist, 0);
                distToCount.put(dist, count + 1);
            }
            for (int count : distToCount.values()) {
                if (count > 1) {
                    result += count * (count - 1);
                }
            }
        }
        return result;
    }
}

Complexity

• Time: n2
• Space: n

[CarrieyqZhang]

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], y = points[i][1] - points[j][1];
                int dist = x * x + y * y;
                map.put(dist, map.getOrDefault(dist, 0) + 1);
            }
            for (int dist : map.keySet()) {
                int cnt = map.get(dist);
                ans += cnt * (cnt - 1);
            }
        }
        return ans;
    }

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

[caterpillar-0]

思路

两层循环遍历计算之间的距离，将距离出现个数存储在unordered_map中，再使用排列组合

代码

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

复杂度分析

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

[wychmod]

思路

暴力解法是三层循环遍历，用空间换时间，用哈希表，将距离都存进去，然后数量可以表示为当前距离有的数量n，n*（n-1），这样两层循环就ok了。

代码

class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:
        if len(points) < 3:
            return 0
        res = 0
        for i in range(len(points)):
            dic = {}
            for j in range(len(points)):
                if j == i:
                    continue
                dis = (points[j][0]-points[i][0])**2 + (points[j][1]-points[i][1])**2
                dic[dis] = dic.get(dis, 0)+1
            for val in dic.values():
                res += val*(val-1)

        return res

复杂度

时间复杂度On^2 空间复杂度On

[Joyce94]

思路 1、三层循环优化为两层； 2、哈希表的一个作用是空间换时间； 3、统计以i为目标节点，其他节点与目标节点的距离，对不同距离的节点个数计数，比如距离为3的节点个数有n个，那么i为第一个节点，距离为3的组合下，第二个节点j有n种可能，第三个节点k有n-1种可能，整个距离为3的组合有n*(n-1)种可能。

代码

class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:
        ## 排列组合 
        n = len(points)
        count = 0 
        for i in range(n):
            ## 计算与i的不同距离的个数
            dic = collections.defaultdict(int)
            for j in range(n): ##注意范围
                dist = math.pow((points[i][0]-points[j][0]), 2) + math.pow((points[i][1]-points[j][1]), 2)
                dic[dist] += 1 
            for k,v in dic.items():
                count += v*(v-1)
        return count 

[zqwwei]

Idea

关键想到permutation: nP2 = n * n - 1 和 需要边的长度可以用哈希表储存

Code

    def numberOfBoomerangs(self, points: List[List[int]]) -> int:
        booms = 0
        map_ = dict()

        def get_dist(a, b):
            return (a[0] - b[0]) * (a[0] - b[0]) + (a[1] - b[1]) * (a[1] - b[1])

        for i in points:
            for j in points:
                d = get_dist(i, j)
                # nP2 = n!/(n-2)! = n * (n - 1) found n = 1, nP2 = 0
                map_[d] = map_.get(d, 0) + 1     

            for val in map_.values():
                booms += val * (val - 1)

            map_.clear()

        return booms

[linjunhe]

• 思路

  • 以一个point作为pi，算其它所有点到它的距离；
  • 以距离为key，频次为value存入hashtable
  • 如果频次为2，说明有两个点到pi距离一样，这时boomerang数量为2*1=2
  • 如果频次为3，boomerang数量为3*2=6

  • 代码

    -

              class Solution:
                  def numberOfBoomerangs(self, points: List[List[int]]) -> int:
                      num = 0
                      for pi in points:
                          hashtable= defaultdict(int)
                          for pj in points:
                              dist = (pi[0]-pj[0])**2 + (pi[1]-pj[1])**2
                              hashtable[dist] += 1
                          for n in hashtable.values():
                              num += n * (n-1)
                      return num

  • 复杂度分析

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

[currybeefer]

思路：我是彩笔，又参考了官方题解。 总的来说就是需要寻找到三个点的组合，i，j，k，其中对于i来说，j和k于i的距离必须相等。 暴力枚举法需要三重循环，这样的话时间复杂度是O(n^3)太不划算了。 因此我们可以想到排列组合问题，如果将i点固定，在剩下的点中筛选出距离与i相等的点的集合。 假设离i距离为a的点有n个，那么就是从n个里边选出顺序的两个点与i组合，即排列组合问题，An2。

int numberOfBoomerangs(vector<vector<int>>& points) 
    {
        int res=0;

        for(int i=0;i<points.size();i++)
        {
            unordered_map<int,int> map;
            for(int j=0;j<points.size();j++)
            {
                int dis=Distance(points[i],points[j]);
                map[dis]++;
            }
            for(auto p=map.begin();p!=map.end();p++)
            {
                res+=p->second*(p->second-1);
            }
        }
        return res;
    }

    int Distance(vector<int> a, vector<int> b)
    {
        int x=a[0]-b[0];
        int y=a[1]-b[1];

        return x*x+y*y;
    }

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

[carterrr]

class Solution { public int numberOfBoomerangs(int[][] points) { 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++) { if(i == j) continue; int a = points[j][0] - points[i][0]; int b = points[j][1] - points[i][1]; int dist = b b + a a; map.put(dist, map.getOrDefault(dist, 0) + 1); } for(Integer c : map.values()) { if(c > 1) { res += c (c - 1); // Cn2 组合公式 n (n - 1) / 2 这里就应该算是两种 因而去掉 / 2 } } map.clear(); } return res; } }

[wenliangchen]

Idea

use hash map to have the record, and then calculate the distance.

code

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

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

        for(int val : map.values()) {
            res += val * (val-1);
        }            
        map.clear();
    }

    return res;
}

private int getDistance(int[] a, int[] b) {
    int dx = a[0] - b[0];
    int dy = a[1] - b[1];

    return dx*dx + dy*dy;
}

}

[MoonLee001]

思路

（没看懂题目，看了答案写的），使用哈希表记录每组距离的个数，然后遍历哈希表，计算每选出2个数的组合数

代码

var numberOfBoomerangs = function(points) {
    let ans = 0;
    for (let p of points) {
        const map = new Map();
        for (let q of points) {
            const dis = Math.pow((p[0] - q[0]), 2) + Math.pow((p[1] - q[1]), 2); 
            map.set(dis, (map.get(dis) || 0) + 1);
        }
        for (let [key, value] of map.entries()) {
            ans += (value - 1) * value;
        }
    }
    return ans;
};

复杂度分析

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

[LQyt2012]

思路

计算每一个点到其他点的距离，用map存储相同距离的点的个数。然后从距离相同的点计算排列数m*(m-1)

代码

class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:
        ans = 0
        for p in points:
            dist_map = collections.defaultdict(int)
            for q in points:
                dist = (p[0]-q[0]) ** 2 + (p[1]-q[1]) ** 2
                dist_map[dist] += 1
            for m in dist_map.values():
                ans += m*(m-1)
        return ans

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

复杂度分析

时间复杂度：O(N*N)
空间复杂度：O(N)

[Ellie-Wu05]

思路二：Hash Table

看题解的，每次做哈希表的时候都不清楚存的内容是什么？ 是value，index，距离等等。。。还需要多练习

代码

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

        n = len(points)
        res = 0

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

            for count in m.values():
                res += count*(count-1)

        return res

复杂度

时间 On^2 \ 空间 On

[physicshi]

思路

Rust 和 JS

hashmap，对每一个点，求剩下的点到该点的距离，缓存距离，缓存距离会作为边，有两个及以上相同的，就可以作为一个回旋镖，求其组合数就是从该点出发构成的回旋镖数

代码

var numberOfBoomerangs = function (points) {
  let count = 0;
  function calcDist(a, b) {
    return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2;
  }
  for (let i = 0; i < points.length; i++) {
    const map = {};
    for (let j = 0; j < points.length; j++) {
      if (points[i] != points[j]) {
        let dist = calcDist(points[i], points[j]);
        map[dist] = (map[dist] || 0) + 1;
      }
    }
    for (let d in map) {
      let num = map[d];
      if (num > 1) {
        count += num * (num - 1);
      }
    }
  }
  return count;
};

use std::collections::HashMap;

impl Solution {
    pub fn calaDist(x: &Vec<i32>, y: &Vec<i32>) -> i32 {
        let distx = x[0] - y[0];
        let disty = x[1] - y[1];
        distx * distx + disty * disty
    }
    pub fn number_of_boomerangs(points: Vec<Vec<i32>>) -> i32 {
        let mut count: i32 = 0;
        for (i, ival) in points.iter().enumerate() {
            let mut map = HashMap::new();
            for (j, jval) in points.iter().enumerate() {
                if i == j {
                    continue;
                }
                let dist = Self::calaDist(ival, jval);
                *map.entry(dist).or_insert(0) += 1;
            }
            for (_, num) in map.iter() {
                if *num > 1 {
                    count += num * (num - 1);
                }
            }
        }
        count
    }
}

复杂度

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

[duke-github]

思路

双重循环遍历  将循环外层坐标点和内层坐标点的距离的平方作为key存入map中 
当这个长度再次出现的时候 将出现的次数作为value存入hash表 并将之前出现的次数*2加给总的出现次数

复杂度

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

代码

    public int numberOfBoomerangs(int[][] points) {
        Map<Integer, Integer> map = new HashMap<>();
        int ans = 0;
        for (int i = 0; i < points.length; i++) {
            map = new HashMap<>();
            for (int j = 0; j < points.length; j++) {
                if (i == j) continue;
                int len = (points[i][0] - points[j][0]) * (points[i][0] - points[j][0]) +
                 (points[i][1] - points[j][1]) * (points[i][1] - points[j][1]);
                if (map.containsKey(len)) {
                    ans += map.get(len) * 2;
                }
                map.put(len, map.getOrDefault(len, 0) + 1);
            }
        }
        return ans;
    }

[PFyyh]

题目地址(447. 回旋镖的数量)

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

题目描述

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

返回平面上所有回旋镖的数量。

 

示例 1：

输入：points = [[0,0],[1,0],[2,0]]
输出：2
解释：两个回旋镖为 [[1,0],[0,0],[2,0]] 和 [[1,0],[2,0],[0,0]]

示例 2：

输入：points = [[1,1],[2,2],[3,3]]
输出：2

示例 3：

输入：points = [[1,1]]
输出：0

 

提示：

n == points.length
1 <= n <= 500
points[i].length == 2
-104 <= xi, yi <= 104
所有点都 互不相同

前置知识

• 哈希表

• 两点距离

  公司

• 暂无

思路

关键点

• 应该存 KV = 距离,个数
• 组合可能为n(n-1)

代码

• 语言支持：Java

Java Code:

class Solution {
    public int numberOfBoomerangs(int[][] points) {
        //判断数组长度是否小于等于二，如果是则返回
        if(points.length<=2){
            return 0;
        }
        int sum = 0;

        //定义哈希表 key存储距离，value存储数量。最后返回的key的数量就是sum = value*(value-1)
        Map<Integer,Integer> map = new HashMap<>();
        for(int i=0;i<points.length;i++){
            for(int j=0;j<points.length;j++){
                int x = points[j][0]-points[i][0];
                int y = points[j][1]-points[i][1];
                int dist =x*x+y*y;
                 map.put(dist, map.getOrDefault(dist, 0) + 1);
            }
            for(int value : map.values()){
                sum+=value*(value-1);
            }
            map.clear();
        }

        return  sum;
    }
}

复杂度分析

令 n 为数组长度。

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

[L-SUI]

/**
 * @param {number[][]} points
 * @return {number}
 */
var numberOfBoomerangs = function(points) {
    let ans = 0;
    for (const p of points) {
        const cnt = new Map();
        for (const q of points) {
            const dis = (p[0] - q[0]) * (p[0] - q[0]) + (p[1] - q[1]) * (p[1] - q[1]);
            cnt.set(dis, (cnt.get(dis) || 0) + 1);
        }
        for (const [_, m] of cnt.entries()) {
            ans += m * (m - 1);
        }
    }
    return ans;
};

[miss1]

思路

两点[x1, y1]和[x2, y2]之间的距离 d = (x1-x2)² + (y1-y2)², d开根就是两点的距离。

排列：从n个数中取出m个数能组合的排列数 -> n(n-1)(n-2)...(n-m+1)

两个循环遍历，计算出每个点到其它点之间的距离，存到map中，距离distance为key值，value为跟当前点距离相同的点的个数。固定当前点为第一个数，取出具有相同distance的点的个数 n, 从n中取两个数能组合的排列数就是当前的结果数量。

代码

/**
 * @param {number[][]} points
 * @return {number}
 */
var numberOfBoomerangs = function(points) {
  let map = new Map(), count = 0;
  let getDistance = function(p1, p2) {
    let x = p1[0] - p2[0];
    let y = p1[1] - p2[1];
    return x * x + y * y;
  }
  for (let i = 0; i < points.length; i++) {
    for (let j = 0; j < points.length; j++) {
      let distance = getDistance(points[j], points[i]);
      if (map.has(distance)) map.set(distance, map.get(distance) + 1);
      else map.set(distance, 1);
    }
    map.forEach((val, key) => { if (val > 1) count += val * (val - 1); });
    map.clear();
  }
  return count;
};

复杂度分析

• time: O(n²)
• space: O(n)

[zhulin1110]

题目地址(447. 回旋镖的数量)

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

题目描述

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

返回平面上所有回旋镖的数量。

示例 1：

输入：points = [[0,0],[1,0],[2,0]]
输出：2
解释：两个回旋镖为 [[1,0],[0,0],[2,0]] 和 [[1,0],[2,0],[0,0]]

示例 2：

输入：points = [[1,1],[2,2],[3,3]]
输出：2

示例 3：

输入：points = [[1,1]]
输出：0

提示：

n == points.length
1 <= n <= 500
points[i].length == 2
-104 <= xi, yi <= 104
所有点都 互不相同

思路1

三层循环，暴力解法

代码1

• 语言支持：JavaScript

JavaScript Code:

/**
 * @param {number[][]} points
 * @return {number}
 */
var numberOfBoomerangs = function(points) {
    if (points == null || points.length <= 2)
        return 0;

    let res = 0;

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

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

            if (i == j)
                continue;

            for (let k = 0; k < points.length; k++) {

                if (k == i || k == j)
                    continue;

                if (getDistance(points[i], points[j]) == getDistance(points[i], points[k]))
                    res++;
            }
        }
    }

    return res;
}
let x = [];
let y = [];
function getDistance(x, y) {

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

    return x1 * x1 + y1 * y1;

}

复杂度分析1

令 n 为数组长度。

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

  思路2 看题解的。。

  哈希表+ 枚举

代码2

• 语言支持：JavaScript

JavaScript Code:

/**
 * @param {number[][]} points
 * @return {number}
 */
var numberOfBoomerangs = function(points) {
    let ans = 0;
    for (let p of points) {
        const map = new Map();
        for (let q of points) {
            const dis = Math.pow((p[0] - q[0]), 2) + Math.pow((p[1] - q[1]), 2); 
            map.set(dis, (map.get(dis) || 0) + 1);
        }
        for (let [_, value] of map.entries()) {
            ans += (value - 1) * value;
        }
    }
    return ans;
};

复杂度分析2

令 n 为数组长度。

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

[mo660]

思路

枚举和哈希表

代码

class Solution {
public:
    int numberOfBoomerangs(vector<vector<int>>& points) {
        int ans = 0;
        for(auto &it : points){
            map<int,int>mp;
            for(auto &q:points){
                int dist = (it[0] - q[0])*(it[0] - q[0]) + (it[1] - q[1])*(it[1] - q[1]);
                mp[dist]++;
            }
            for(auto &res : mp){
            ans += res.second*(res.second - 1);
            }
        }
        return ans;
    }
};

[weihaoxie]

思路

哈希表+排列组合

代码

class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:
        all_count = 0
        for p in points:
            dist_2_count = {}
            for b in points:
                dist  = (p[0]-b[0])*(p[0]-b[0])+(p[1]-b[1])*(p[1]-b[1])
                if dist in dist_2_count:
                    dist_2_count[dist] += 1
                else:
                    dist_2_count[dist] = 1
            for item in dist_2_count:
                all_count += dist_2_count[item]*(dist_2_count[item]-1)
        return all_count

复杂度

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

[revisegoal]

哈希表 + 枚举

每个点枚举通过该点的边距离并存入哈希表对距离计数，相同距离则形成“回旋镖”，每个点枚举完后，遍历哈希表，每个值的全排列相加则是通过该点的元组数，最后清空表再对下个点进行距离枚举

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 = getDis(points[i], points[j]);
                map.put(dis, map.getOrDefault(dis, 0) + 1);
            }
            for (Integer value : map.values()) {
                res += value * (value - 1);
            }
            map.clear();
        }
        return res;
    }

    int getDis(int[] p, int[] q) {
        return (p[0] - q[0]) * (p[0] - q[0]) +
            (p[1] - q[1]) * (p[1] - q[1]);
    }
}

• time: O(n^2)
• space: O(n)

[sallyrubyjade]

思路

查表

代码

/**
 * @param {number[][]} points
 * @return {number}
 */
var numberOfBoomerangs = function(points) {
        let ans = 0;
        for (const p of points) {
            const m = new Map();
            for (const q of points) {
            //统计距离当前点相同距离的数量 加入map中
            const dis = (p[0] - q[0]) * (p[0] - q[0]) + (p[1] - q[1]) * (p[1] - q[1]);
            m.set(dis, (m.get(dis) || 0) + 1);
        }

        for (const [_, item] of m.entries()) {
            ans += item * (item - 1);
        }
    }
    return ans;
};

[EggEggLiu]

思路

遍历节点，将所有节点与其距离存在哈希表中，取哈希表中的val值输出

代码

var numberOfBoomerangs = function(points) {
    let res = 0;
    for (let i = 0; i < points.length; i++) {
        let hashMap = new Map();
        for (let j = 0; j < points.length; j ++) {
            let dis = distance(i, j);
            if (hashMap.has(dis)) {
                hashMap.set(dis, hashMap.get(dis) + 1);
            } else {
                hashMap.set(dis, 1);
            }
        }
        for (let val of hashMap.values()) {
            res += val * (val - 1);
        }
    }
    function distance(i, j) {
        return Math.pow(points[i][0] - points[j][0], 2) + Math.pow(points[i][1] - points[j][1], 2);
    }
    return res;
};

[houyanlu]

思路

三遍for循环枚举所有的值超过了时间限制 问题就需要精简时间的计算, 问题可以转化为：距离A点所有的距离为x的点都可以两两组合为三元组

代码

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

        unordered_map<int, int> map;
        int ans = 0;

        for (int i = 0; i < points.size(); i++) {
            map.clear();   //这一行很重要，每次循环算一个点的
            for (int j = 0; j < points.size(); j++) {
                int distance = getInstance(points[i], points[j]);
                map[distance]++;
            }

            for (const auto&[key, val] : map) {
                ans += val * (val - 1);
            }
        }
        return ans;
}

int getInstance(const vector<int>& point1, const vector<int>& point2) {   
        int x1 = point1[0];
        int y1 = point1[1];

        int x2 = point2[0];
        int y2 = point2[1];

        return (x2 - x1) * (x2 - x1) + (y1 - y2) * (y1 - y2);
}

};

复杂度分析

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

[Orangejuz]

思路

暴力枚举

代码

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

复杂度分析

时间复杂度 O(N^2)

空间复杂度 O(N)

[KWDFW]

Day21

447、回旋镖的数量

javascript #哈希表

思路

1、设有m个点到points[i]的距离相同

2、从m点中选出两个点作为一个回旋镖

3、个数为组合数：m*（m-1）

4、遍历points，将每个距离的出现次数记录到哈希表中

5、遍历哈希表，求和

题解

代码

var numberOfBoomerangs = function(points) {
    let ans = 0;//记录回旋镖数量
    for (const p of points) {//外层循环
        const cnt = new Map();//建立哈希表
        for (const q of points) {
            const dis = (p[0] - q[0]) * (p[0] - q[0]) + (p[1] - q[1]) * (p[1] - q[1]);
            cnt.set(dis, (cnt.get(dis) || 0) + 1);
            //将每个距离的出现次数记录到哈希表中
        }
        for (const [_, m] of cnt.entries()) {
            ans += m * (m - 1);
            //遍历哈希表，求出回旋镖个数
        }
    }
    return ans;
};

复杂度分析

时间复杂度：O(n2)

空间复杂度：O(n)

[577961141]

447. 回旋镖的数量

题目链接

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

题目思路

欧式算法： 思路： 采用哈希表的方式存储，欧式算法的结果。过程如下

1. 两次遍寻，两次遍寻的key不能是同一个，同一个就跳过，因为本身不计算欧式距离
2. 当key不同时，将val传入计算欧式距离的方法distance里面
3. 然后用哈希表存起来，key为方法distance结果的值，value为次数
4. 假如出现距离为3的次数为2，那么组合总共有2*(2-1),按照这个公式累加其他距离出现的次数即可等到正确答案

   题目的题解code

   
   <?php

class Solution {

/**
 * @param Integer[][] $points
 * @return Integer
 */
function numberOfBoomerangs($points)
{
    $res = 0;
    foreach ($points as $key1 => $val1) {
        $map = []; // 建立一个哈希表
        foreach ($points as $key2 => $val2) {
            if ($key1 == $key2) { // 如果key相等就跳过，不计算自身的数据
                continue;
            }
            $temp = $this->distance($val1, $val2); // 欧式距离
            $map[$temp] = isset($map[$temp]) ? $map[$temp] + 1 : 1; // 用哈希表记录相同的欧式距离
        }
        foreach ($map as $item) {
            $res += $item * ($item - 1); // 每个符合距离的欧式距离的个数= n*(n-1)
        }

    }

    return $res;
}

/**
 * 欧式距离算法，不需要带根号
 *
 * @param $i
 * @param $j
 * @return float|int
 */
private function distance($i, $j)
{
    return ($i[0] - $j[0]) * ($i[0] - $j[0]) + ($i[1] - $j[1]) * ($i[1] - $j[1]);
}

}

## 时间和空间复杂度
时间复杂度：O(n^2),循环两次
空间复杂度：O(n)，最坏的情况下存储n个节点

[liuguang520-lab]

思路

哈希表以距离作为key，出现一样的距离就对value值加1

code

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(n2)
• 空间复杂度O(n)

[All-Sunday]

思路

先遍历数组，统计所有点到points[i]的距离；

将每个距离出现的次数记录在哈希表中；

遍历哈希表，累加排列组合数。

代码

class Solution {
    public int numberOfBoomerangs(int[][] points) {
        int res = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for(int[] p : points){
            for(int [] q : points){
                int distance = (p[0] - q[0]) * (p[0] - q[0]) + (p[1] - q[1]) * (p[1] - q[1]);
                map.put(distance, map.getOrDefault(distance, 0) + 1);
            }

            for(int value : map.values()){
                res += value * (value - 1);
            }

            map.clear();
        }
        return res;
    }
}

复杂度分析

• 时间复杂度：O(n^2)，双重循环。
• 空间复杂度：O(n)。

[duantao74520]

思路：

1. 统计每个节点与其他节点的距离

2. ​ // 计算以当前节点为中心，有多少个回旋镖。

   ​ // 例如当前节点与其他节点的距离为 0 1 2 2 3 3 3

   ​ // 则 当前节点的回旋镖有 A22 + A23 = 2+6 = 8个。 A23是距离为3的，选任意两个，并且有序的

代码：

class Solution {
public:
    int numberOfBoomerangs(vector<vector<int>>& points) {
        // 统计每个节点与其他节点的距离
        vector<vector<int>> len_vec;
        for (const auto& point1 : points) {
            std::vector<int> len;
            for(const auto& point2: points) {
                len.emplace_back(pow((point1[0]- point2[0]), 2) + pow((point1[1]- point2[1]), 2));
            }
            len_vec.push_back(len);
        }
        // 计算以当前节点为中心，有多少个回旋镖。
        // 例如当前节点与其他节点的距离为 0 1 2 2 3 3 3
        // 则 当前节点的回旋镖有 A22 + A23 = 2+6 = 8个。  A23是距离为3的，选任意两个，并且有序的
        int total_len = 0;
        for (const auto& vec : len_vec) {
            map<int, int> len_2_size;
            for (int num : vec) {
                len_2_size[num] ++;
            }
            for (const auto [len ,size] : len_2_size) {
                if (size >=2) {
                    total_len += size*(size-1);
                }
            }
        }
        return total_len;
    }
};

复杂度：

时间 O(N2)

空间 O(N2)