https://leetcode.com/problems/number-of-boomerangs/description/
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]
(inclusive).
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]]
给定一个 vector, 里面包含 n 个点, 如果 3 个点(索引分别为 i, j, k)满足 dis(p[i], p[j])
等于 dis(p[i], p[k])
, 那么就称 (i, j, k)
为一个 boomerang. 注意 tuple 中的元素的顺序. 现在要统计 boomerang 的个数.
思路: 由于 tuple 中有 3 个元素, 可以考虑先固定索引 i, 然后寻找符合条件的 j 和 k. 这样的话, 假设到 i 的节点有 m 个 (m >= 2)
, 那么就可以从这 m 个节点中选出 2 个来, 和 i
一起组成一个 boomerang, 那么总共有 (m * (m - 1))
中选择.
class Solution {
private:
int distance(pair<int, int> &p1, pair<int, int> &p2) {
int a = p1.first - p2.first;
int b = p1.second - p2.second;
return a * a + b * b;
}
public:
int numberOfBoomerangs(vector<pair<int, int>>& points) {
int res = 0;
const int rows = points.size();
for (int i = 0; i < rows; ++i) {
// 注意此时 record 在 i 固定时产生, 第二个参数保存索引.
unordered_map<int, vector<int>> record;
for (int j = 0; j < rows; ++j) {
if (j == i) continue; // 节点自身不用考虑.
record[distance(points[j], points[i])].push_back(j);
}
// record 中此时保存的是到 points[i] 的距离相同的所有节点.
for (auto &iter : record) {
int size = iter.second.size();
if (size >= 2) res += size * (size - 1);
}
}
return res;
}
};
上面速度稍慢, 改成下面加快速度: 使用了关联型容器的 clear 方法.
class Solution {
private:
int distance(pair<int, int> &p1, pair<int, int> &p2) {
int a = p1.first - p2.first;
int b = p1.second - p2.second;
return a * a + b * b;
}
public:
int numberOfBoomerangs(vector<pair<int, int>>& points) {
int res = 0;
// record的第二个参数保存索引的个数
unordered_map<int, int> record;
const int rows = points.size();
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < rows; ++j) {
if (j != i)
record[distance(points[j], points[i])] ++;
}
// 如果 record 中只有一个索引, 结果为 0.
for (auto &iter : record)
res += iter.second * (iter.second - 1);
record.clear();
}
return res;
}
};