【基础篇 - Day 21】 2023-03-05 - 447. 回旋镖的数量 （04. 哈希表）

[threedayAAAAA]

给定平面上 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 所有点都 互不相同

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/number-of-boomerangs 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

[threedayAAAAA]

思路

暴力循环，每次都获取当前节点与除自己以外所有节点的距离，如果存在有距离相同的点并且大于1个 那么就存在 n * (n - 1)种情况，n为距离相同的点的个数

代码

function numberOfBoomerangs(points: [number, number][]): number {
    let result = 0
    for(const a of points){
        const disMap = {}
        for(const b of points){
             if (a !== b) {
                const dist = calcDistOf2Points(a, b);
                disMap[dist] = disMap[dist] ? disMap[dist] + 1 : 1
            }
        }
        for (const dist in disMap) {
            if(disMap[dist] > 1){
                result += disMap[dist] * (disMap[dist] - 1)
            }
        };
    }
    return result
};

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

时空复杂度

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

[MiumMi]

思路

双重循环，哈希表记录每个点在数组其他点位的距离

代码

function numberOfBoomerangs(points: number[][]): number {
  // 欧式距离计算：sqrt( (x1-x2)^2+(y1-y2)^2 ) 这里计算可以直接简化为(x1-x2)^2 + (y1-y2)^2
  let result = 0;
  points.forEach(item => {
      const hash = {};
      points.forEach(point => {
          if (point === item) {
              return;
          }
          const dist = Math.pow(item[0] - point[0], 2) + Math.pow(item[1] - point[1], 2);
          if (!hash[dist]){
              hash[dist] = 0;
          }
          hash[dist]++;
      });
      Object.keys(hash).forEach(key => {
          result += hash[key] * (hash[key] - 1);
      })
  })
  return result;
};

---

分析

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

[yunliuyan]

思路

• 哈希表储存每个坐标点的与其他坐标的距离，若有相等的距离，则结果值m*(m-1)

代码

function numberOfBoomerangs(points: number[][]): number {
    let res = 0;
    for(const point of points) {
        const hashMap: Map<number, number> = new Map();
        for (const otherPoint of points) {
            // 开根和平方一样
            const distance = Math.pow(point[0] - otherPoint[0], 2) + Math.pow(point[1] - otherPoint[1], 2);
            hashMap.set(distance, (hashMap.get(distance) ?? 0) + 1);
        }
        hashMap.forEach(item => {
            res += item * (item - 1);
        });
        hashMap.clear();
    }
    return res;
};

时空复杂度

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