跳至主要內容

447. 回旋镖的数量

447. 回旋镖的数量

🟠   🔖  数组 哈希表 数学  🔗 力扣open in new window LeetCodeopen in new window

题目

You are given n points in the plane that are all distinct , where points[i] = [xi, yi]. A boomerang is a tuple of points (i, j, k) such that the distance between i and j equals the distance between i and k(the order of the tuple matters).

Return the number of boomerangs.

Example 1:

Input: points = [[0,0],[1,0],[2,0]]

Output: 2

Explanation: The two boomerangs are [[1,0],[0,0],[2,0]] and [[1,0],[2,0],[0,0]].

Example 2:

Input: points = [[1,1],[2,2],[3,3]]

Output: 2

Example 3:

Input: points = [[1,1]]

Output: 0

Constraints:

  • n == points.length
  • 1 <= n <= 500
  • points[i].length == 2
  • -10^4 <= xi, yi <= 10^4
  • All the points are unique.

题目大意

给定平面上 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
  • -10^4 <= xi, yi <= 10^4
  • 所有点都 互不相同

解题思路

  1. 定义回旋镖

    • 题目要求找到所有满足 (i, j, k) 的 回旋镖（Boomerang），即满足： dist(i, j) == dist(i, k) 其中 dist(i, j) 表示点 i 和 j 之间的距离。

  2. 计算点对之间的距离

    • 我们可以使用 平方欧几里得距离 来避免浮点运算： dist(i, j) = (x1 - x2)^2 + (y1 - y2)^2
    • 对于每个点 i，统计它与其他点的距离出现的次数。

  3. 利用哈希表统计相同距离的点

    • 对于每个点 i，用哈希表 count 统计到其他点的距离：
      • count[dist] 记录当前 i 点下，出现相同 dist 的点的个数。
    • 若 count[dist] = m，那么从这些点中选出两个点 (j, k) 组成回旋镖的方案数为： m * (m - 1) 因为 j -> k 和 k -> j 是不同的排列。

  4. 遍历所有点，累加所有方案

    • 对于每个点 i，遍历 j 计算所有 dist(i, j) 并更新 count[dist] 统计数量。
    • 计算 m * (m - 1) 并累加到 res。

复杂度分析

  • 时间复杂度： O(n^2)
    • 两层循环计算所有点对的距离，共 O(n^2) 次。
    • count 哈希表的插入和查询平均时间复杂度为 O(1)，整体 O(n^2)。
  • 空间复杂度： O(n)
    • count 哈希表最多存储 n 个不同的距离（极端情况）。
    • 由于 count 每轮 i 计算完成后都会清空，额外空间复杂度为 O(n)。

代码

/**
 * @param {number[][]} points
 * @return {number}
 */
var numberOfBoomerangs = function (points) {
	const n = points.length;
	let res = 0;

	for (let i = 0; i < n; i++) {
		let count = new Map();
		for (let j = 0; j < n; j++) {
			if (i === j) continue;
			const [x1, y1] = points[i];
			const [x2, y2] = points[j];
			const dist = (x1 - x2) ** 2 + (y1 - y2) ** 2;
			const cnt = count.get(dist) || 0;
			res += 2 * cnt; // 两个排列： (j, k) 和 (k, j)
			count.set(dist, cnt + 1);
		}
	}
	return res;
};

相关题目

题号标题题解标签难度力扣
356直线镜像 🔒数组 哈希表 数学🟠🀄️open in new window 🔗open in new window