LeetCode 447. Number of Boomerangs(回旋镖的数量)
题目描述
Given n points in the plane that are all pairwise distinct, 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).
Find the number of boomerangs. You may assume that n will be at most 500 and coordinates of points are all in the range -10000, 10000.
Example:
Input:
[[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]]
解法一
思路
这题换个说法就是,在二维坐标系下有若干个点,求满足x
和y
的距离与y
和z
的距离相等的三个点x
、y
和z
的数目。
想要知道距离是否相等,那首先就要知道距离的值,这样就免不了要遍历了。即对于每个点y
,遍历其他的点,并寻找不同的点x
和z
,满足x
和y
的距离与y
和z
的距离相等。怎么来统计距离相等的点的数目呢?这里有一个优化的方法,对于点y
,遍历其他点时,我们只需要用一个Map来维护(距离, 点的个数)
这样的键值对。遍历完成后再遍历这个Map,如果值为2,则代表有两个点满足要求,记录满足要求的(x, y, z)
为2(因为题目要求考虑点的顺序,所以(x, y, z)
和(z, y, z)
都分别满足题目要求);而如果值大于2,则代表有多个点满足要求,而且其中任意两个点的排列(考虑到顺序)都是符合题意的。这样就得到了以y
为中心点的满足题目要求的情况数目,遍历完所有的点即得到最终结果。
Python
class Solution:
def numberOfBoomerangs(self, points):
"""
:type points: List[List[int]]
:rtype: int
"""
result = 0
for point_a in points:
distances = {}
for point_b in points:
distance = (point_a[0] - point_b[0]) ** 2 + (point_a[1] - point_b[1]) ** 2
distances[distance] = distances.get(distance, 0) + 1
result += sum(item * (item - 1) for item in distances.values())
return result
Java
class Solution {
public int numberOfBoomerangs(int[][] points) {
int result = 0;
for (int[] pointA : points) {
Map<Integer, Integer> distances = new HashMap<>();
for (int[] pointB : points) {
int distance = (pointA[0] - pointB[0]) * (pointA[0] - pointB[0]) + (pointA[1] - pointB[1]) * (pointA[1] - pointB[1]);
distances.put(distance, distances.getOrDefault(distance, 0) + 1);
}
for (int item : distances.values()) {
result += item * (item - 1);
}
}
return result;
}
}
C++
class Solution {
public:
int numberOfBoomerangs(vector<pair<int, int>> &points) {
int result = 0;
for (auto &pointA : points) {
map<int, int> distances;
for (auto &pointB : points) {
int distance = (pointA.first - pointB.first) * (pointA.first - pointB.first) +
(pointA.second - pointB.second) * (pointA.second - pointB.second);
distances[distance]++;
}
for (auto &item : distances) {
result += item.second * (item.second - 1);
}
}
return result;
}
};