题目:给定平面上 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
提示:
class Solution {
public:
// 欧氏距离
int osDistance(vector<int> point1, vector<int> point2){
return (point1[0]-point2[0])*(point1[0]-point2[0]) + (point1[1]-point2[1])*(point1[1]-point2[1]);
}
int numberOfBoomerangs(vector<vector<int>>& points) {
// 点的数量少于3不存在回旋镖,直接返回0
if(points.size() < 3){
return 0;
}
int count = 0;
// 第一个循环用于获取第一个点
for(auto base: points){
// 第二循环用于获取第二个点
for(auto point1:points){
// 第二点不可以与第一个一样
if(point1 == base){
continue;
}
// 计算第一个与第二点之间的距离
int D1 = osDistance(base, point1);
// 第三个循环用于获取第三点
for(auto point2:points){
// 第三个点不可以第一、二个点重复
if(point2 == base or point2 == point1){
continue;
}
// 计算第一个点与第三个点之间的距离
int D2 = osDistance(base, point2);
// 如果D1==D2,增加一个回旋镖数量
if(D1 == D2){
count++;
}
}
}
}
return count;
}
};
超出时间限制
时间复杂度:O(n3)
空间复杂度:O(1)
class Solution {
public:
int numberOfBoomerangs(vector<vector<int>> &points) {
int ans = 0;
for (auto &p : points) {
unordered_map<int, int> cnt;
for (auto &q : points) {
int dis = (p[0] - q[0]) * (p[0] - q[0]) + (p[1] - q[1]) * (p[1] - q[1]);
++cnt[dis];
}
for (auto &[_, m] : cnt) {
ans += m * (m - 1);
}
}
return ans;
}
};
作者:力扣官方题解
链接:https://leetcode.cn/problems/number-of-boomerangs/solutions/994189/hui-xuan-biao-de-shu-liang-by-leetcode-s-lft5/
来源:力扣(LeetCode)
通过使用哈希表,实现以空间换取时间。
假设某个距离的数量为m,由于题目说明需要考虑元组中元素的顺序,所以这个距离对应的回旋镖的数量为A2m。
A2m = (m*(m-1)) / 2
时间复杂度:O(n2)
空间复杂度:O(n),哈希表占用的额外空间
2024.1.8