题目描述
思路
代码

leetcode - daily - 447.number-of-boomerangs

September 13, 2021

题目描述

给定平面上 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.com/problems/number-of-boomerangs
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

对每个点 P(x, y), 如果离P点距离为D的点个数为N(N >= 2), 则这N个和P可以构成 N * (N - 1) 个回旋彪数量。(N个取2的排列)

因此,计算每个P点和其它点的距离即可。为减少重复计算,这里使用哈希表,哈希表设计为

Map<D, N>, D 为离P点的长度, N 为离P点长度为D的数量。

PS: 任意两点A1(x1, y1), A2(x2, y2)之间距离D满足 D ^ 2 = (x1 - x2) ^ 2 + (y1 - y2) ^ 2

代码

/**
 * @param {number[][]} points
 * @return {number}
 */
var numberOfBoomerangs = function(points) {
  let mapArr = points.map(() => new Map())
  for (let i = 0; i < points.length; i++) {
    for (let j = i + 1; j < points.length; j++) {
      let dd = getDistance(points[i], points[j])
      mapArr[i].set(dd, mapArr[i].get(dd) ? mapArr[i].get(dd) + 1 : 1)
      mapArr[j].set(dd, mapArr[j].get(dd) ? mapArr[j].get(dd) + 1 : 1)
    }
  }


  let res = 0
  for (let curMap of mapArr) {
    for (let [d, num] of curMap) {
      if (num >= 2) {
        res += num * (num - 1)
      }
    }
  }

  return res
};

// 因为拿distance只为比较, 并不需要真实计算,可以用 distance * distance 表示
function getDistance(p1, p2) {
  const [x1, y1] = p1
  const [x2, y2] = p2
  return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)
}


// console.log(numberOfBoomerangs([[0,0],[1,0],[2,0]]))
  • 时间复杂度: $O(N * N)$, N 为点points的数量
  • 空间复杂度: $O(N * N)$, N 为点points的数量

feiker 少年起而行之