【Day 21 】2024-04-28 - 447. 回旋镖的数量

[azl397985856]

447. 回旋镖的数量

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/number-of-boomerangs/

前置知识

• 哈希表
• 两点间距离计算方法
• 排列组合基础知识

  题目描述

  
  给定平面上  n 对不同的点，“回旋镖” 是由点表示的元组  (i, j, k) ，其中  i  和  j  之间的距离和  i  和  k  之间的距离相等（需要考虑元组的顺序）。

找到所有回旋镖的数量。你可以假设  n 最大为 500，所有点的坐标在闭区间 [-10000, 10000] 中。

示例:

输入: [[0,0],[1,0],[2,0]]

输出: 2

解释: 两个回旋镖为 [[1,0],[0,0],[2,0]] 和 [[1,0],[2,0],[0,0]]

[zhiyuanpeng]

class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:
        ans = 0
        for i, a in enumerate(points):
            distance = collections.defaultdict(int)
            for j, b in enumerate(points):
                if i == j:
                    continue
                dist = (a[0] - b[0])**2 + (a[1] - b[1])**2
                distance[dist] += 1
            #
            for k, v in distance.items():
                if v >=2:
                    ans += v*(v-1)
        return and

Time O(N**2) Space O(N)

[xil324]

var numberOfBoomerangs = function(points) {
    let ans = 0; 
    for(let i= 0; i < points.length; i++) {
        const [x,y] = points[i];
        const countMap = {}; 
        for(const point of points) {
            const squaredDist = (point[0]-x) **2 + (point[1]-y) **2;
            if(squaredDist in countMap) {
                countMap[squaredDist] += 1; 
            }else {
                countMap[squaredDist] = 1; 
            }
        } 
        Object.values(countMap).forEach((val) => {
            ans += val * (val - 1); 
        })
    }
    return ans; 
};

// time complexity: O(n^2); // space complexity: O(n)

[xy147]

js代码

var numberOfBoomerangs = function(points) {
    let ans = 0;
    for (const p of points) {
        const cnt = new Map();
        for (const q of points) {
            const dis = (p[0] - q[0]) * (p[0] - q[0]) + (p[1] - q[1]) * (p[1] - q[1]);
            cnt.set(dis, (cnt.get(dis) || 0) + 1);
        }
        for (const [_, m] of cnt.entries()) {
            ans += m * (m - 1);
        }
    }
    return ans;
};

复杂度分析

时间复杂度：O(n2)

空间复杂度：O(n)

[JackinAI]

遍历所有可能的三个点的组合，检查它们是否形成一个回旋镖。 对于每一对点，找到中点，然后检查中点是否与第三个点形成一个回旋镖。 def numberOfBoomerangs(points):

初始化回旋镖的数量

count = 0

# 遍历所有点的组合
for i in range(len(points)):
    for j in range(i + 1, len(points)):
        # 计算点 i 和点 j 之间的距离的平方
        distance_i_j = (points[i][0] - points[j][0]) ** 2 + (points[i][1] - points[j][1]) ** 2

        # 使用一个字典来统计每个距离的点的数量
        distance_count = {}
        distance_count[distance_i_j] = distance_count.get(distance_i_j, 0) + 1

        # 更新回旋镖的数量
        # 如果有至少两个点与点 i 的距离相同，那么就会形成一个回旋镖
        count += distance_count[distance_i_j]

return count

[Dtjk]

class Solution {
public:
    int numberOfBoomerangs(vector<vector<int>>& points) {
        int ans = 0;
        for (int i = 0; i < points.size(); i++) {
            unordered_map<int, int> mp;
            for (int j = 0; j < points.size(); j++) {
                if (j == i) continue;
                int x = points[i][0] - points[j][0];
                int y = points[i][1] - points[j][1];
                int dist = x * x + y * y;
                mp[dist]++;
            }
            for (auto [dist, cnt] : mp) {
                ans += cnt * (cnt - 1);
            }
        }
        return ans;
    }
};

[hillsonziqiu]

思路

乍一看题目其实没有看明白，就挺离谱的。看了一下解法才知道是咋肥四。 这个就是要找到在直角坐标系中给出的三个点里，是不是有个点在其他两点的垂直平分线上。 这里因为要求距离相等的次数，那么用map存储的话效率最高；

• 外层遍历给出的点。
• 然后内层再遍历所有点。
• 求内层和外层距离差的平方和。
• 排列组合是 C m 2 也就可以写成 m*(m-1)条路径；
• 将所有遍历出的结果求和就得到了最终的返回值。

代码

/*
 * @lc app=leetcode.cn id=447 lang=javascript
 *
 * [447] 回旋镖的数量
 */

// @lc code=start
/**
 * @param {number[][]} points
 * @return {number}
 */
var numberOfBoomerangs = function (points) {
  let result = 0;

  for (const itemPi of points) {
    const countMap = new Map();
    for (const itemPj of points) {
      const key =
        Math.pow(itemPi[0] - itemPj[0], 2) + Math.pow(itemPi[1] - itemPj[1], 2);
      countMap.set(key, (countMap.get(key) || 0) + 1);
    }

    for (const [_, m] of [...countMap]) {
      result += m * (m - 1);
    }
  }

  return result;
};
// @lc code=end

复杂度分析

时间复杂度：O(n^2) 空间复杂度：O(n)

[Martina001]

时间复杂度O(n方)，空间复杂度O(n) class Solution { public int numberOfBoomerangs(int[][] points) { int n = points.length; // 这题自己的思路就是n^2的解法，以为答案会有点技术含量，结果答案也是如此，直接遍历一遍 双循环，把其他点到当前点的距离保存下来 // 需要关注的点是 利用hashMap降低时间复杂度，类似题目：560 和为K的子数组 1248 统计“优美子数组” int res =0; // 公式：因为题目求的是排列，A(a,b)=a!/(a-b)!,所以从m中选两个出来，排列数量为m！/(m-2)！= m(m-1) for(int i = 0; i < n; i++){ HashMap<Double,Integer> map = new HashMap<>(n); int [] curPoint = points[i]; for(int j = 0; j < n; j++){ if(i != j){ double dis = calDistance(points[j],curPoint); map.put(dis,map.getOrDefault(dis,0)+1); } } for(double dis:map.keySet()){ int countDis = map.get(dis); res += countDis(countDis-1); } } return res; }

private double calDistance(int[] x,int []y) {
    return Math.pow(x[0]-y[0],2)+Math.pow(x[1]-y[1],2);
}

}

[yashuning]

题目：447回旋镖的数量 思路： 整体思路：哈希表 代码

    class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:
        def calc(p1,p2):
            return pow(p1[0]-p2[0],2)+pow(p1[1]-p2[1],2)
        dis_map_list = []
        res = 0
        for i in range(points):
            tmp = {}
            for j in range(points):
                if j == i :continue
                dis = calc(points[i],points[j])
                if dis not in tmp:
                    tmp[dis]=0
                tmp[dis] += 1
            dis_map_list.append(tmp.copy())
        for tmp in dis_map_list:
            for k in tmp:
                if tmp[k]>1:
                    res += tmp[k]*(tmp[k]-1)
        return res

时间复杂度：对点集中的点进行了n方的暴力枚举，复杂度为O(n^2)

[franklinsworld666]

思路

首先，固定点X，计算其他所有的点到X的距离，假设距离 D 有 m 个(m>=2), 那么回旋镖有 m(m-1) 从头到尾遍历每一个点，同上计算出总的回旋镖。

代码

class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:
        res = 0
        order_map = dict()
        for i in range(len(points)):
            order_map.clear()
            for j in range(len(points)):
                if j != i:
                    dist = self.__dis(points[i],points[j])
                    if dist not in order_map:
                        order_map[dist] = 1
                    else:
                        order_map[dist] += 1
            for key,value in order_map.items():
                if value >= 2:
                    res += value * (value-1)
        return res
    def __dis(self,pa,pb):
        return (pa[0]-pb[0])*(pa[0]-pb[0])+(pa[1]-pb[1])*(pa[1]-pb[1])

复杂度

• 时间复杂度：O(n *n)
• 空间复杂度：字典最多需要存放 n 个距离，所以O(n)

[CathyShang]

思路： 统计相等的距离的频次，枚举。

class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:
        ans = 0
        for p in points:
            hashmap = defaultdict(int)
            for q in points:
                dis = (p[0]-q[0])*(p[0]-q[0]) + (p[1]-q[1])*(p[1]-q[1])
                hashmap[dis] += 1
            for m in hashmap.values():
                ans += m*(m-1)
        return ans

• Time $O(N^{2})$
• Space $O(N)$

[GReyQT]

class Solution { public: int numberOfBoomerangs(vector<vector>& points) { int n = points.size(); int ans = 0;

    unordered_map<int, int> cnt;

    for (int i = 0; i < n; i++) {
        cnt.clear();
        for (int j = 0; j < n; j++) {
            if (i == j)
                continue;
            int x = (points[i][0] - points[j][0]) *
                    (points[i][0] - points[j][0]);
            int y = (points[i][1] - points[j][1]) *
                    (points[i][1] - points[j][1]);
            cnt[x + y]++;
        }
        for (auto p : cnt) {
            ans += p.second * (p.second - 1);
        }
    }

    return ans;
}

};

[atom-set]

代码

var numberOfBoomerangs = function (points) {
  let ans = 0;
  for (const p of points) {
    const cnt = new Map();
    for (const q of points) {
      const dis = (p[0] - q[0]) * (p[0] - q[0]) + (p[1] - q[1]) * (p[1] - q[1]);
      cnt.set(dis, (cnt.get(dis) || 0) + 1);
    }
    for (const [_, m] of cnt.entries()) {
      ans += m * (m - 1);
    }
  }
  return ans;
};

复杂度分析

• 时间复杂度: O(N^2)
• 空间复杂度: O(N)

[YANGLimbo]

旧思路：三层嵌套，超时了。实际上得到了具体的哪些点的信息，但这些信息是冗余的，并不需要知道具体是哪些点可以组成元组 新思路：对于每个点（作为回旋镖boomerang的中间点，三元组之首项），维护一个哈希表（unorderedmap即可），计算每一种距离出现的次数k，即距离相同的点的数目，则回旋镖的另外两个点组成的对子有k*(k-1)个，每个不同的距离所对应的对子数加起来即是这个点产生的回旋镖数目。 所有点的回旋镖数目加起来就是结果 这样，我们并没有存储具体哪些点产生的元组，我们只关心了不同距离的重复次数，获取到的信息少了，时间也节约了，没有浪费在遍历每一种元组之上。

class Solution {
public:
    int distanceSquare(vector<int>& a, vector<int>& b){
        //return pow( a[0]-b[0],2) +  pow( a[1] -b[1],2);
        return ( a[0]-b[0])* (a[0]-b[0]) + (a[1] -b[1])*(a[1] -b[1]);// 比Pow函数更快
    }
    int numberOfBoomerangs(vector<vector<int>>& points) {
        int n = points.size(); // n 个点
        int count = 0;
        // vector<vector<int>> matrix(n,vector<int>(n,0));
        // for(int i = 0; i < n; i++){
        //     for(int j = i+1; j < n;j++){
        //         matrix[i][j] = distanceSquare(points[i], points[j]);
        //     }
        // }
        // auto getDistance = [&matrix](int a, int b){
        //     if(a<b){
        //         return matrix[a][b];
        //     }else{
        //         return matrix[b][a];
        //     }
        // };
        // for(int i = 0; i < n; i ++){
        //     for(int j = 0; j <n;j++){
        //         if(i == j){
        //             continue;
        //         }
        //         for(int k = 0;k<n;k++){
        //             if( i == k || j == k){
        //                 continue;
        //             }
        //             if(getDistance(i, j) == getDistance(i, k)){
        //                 count++;
        //             }
        //         }
        //     }
        // }
        // return count;
        // 问题：在于三层循环，时间太长，超出限制
        /*
        gpt给出优化方法:使用哈希表维护距离，记录每个距离出现的次数
        某个距离出现了k次则可以产生k*(k-1)个回旋镖
        */
        // 对于每一个点i，也就是三元组的头一个领袖，都维护一个新的哈希表，计算i与其他点的距离以及出现的次数
        for(int i = 0; i < n ;i++){
            unordered_map<int, int> distanceCount;
            int k = 0;
            for(int j = 0;j<n;j++){
                if(i==j){
                    continue;
                }
                distanceCount[distanceSquare(points[i],points[j])]++;
                /*
                在 C++ 中，当你使用 std::unordered_map 并尝试通过键访问值时，如果该键不存在，unordered_map 会自动创建该
                键，并将其值初始化为该值类型的默认值。对于基本数据类型如 int，默认值是 0。
                所以这里不用担心
                */
            }
            // 对每个距离，计算可以形成的回旋镖数量
            for(auto distancePair: distanceCount){
                int k = distancePair.second;
                if(k>1)
                count += k*(k-1);
            }
            /*
            gpt说这里最好判断一下k>1，我认为不判断也可以运行，而且判断也需要消耗资源，gpt这么回答
            计算与判断的成本比较
计算成本：在不进行 k > 1 的判断的情况下，你会执行所有的乘法和加法操作，即使它们的结果是 0。这不仅涉及数学运算，
还可能涉及对内存中 count 变量的不必要更新。当数据集很大时，这些无用的计算会累积成显著的性能损失。

判断成本：if 语句的成本相对较低，尤其是在现代处理器上，分支预测和流水线技术可以极大地减少条件分支的开销。
此外，if 语句的成本通常远低于涉及算术运算和可能的内存访问的成本。

我来记录一下：
不写if(k>1)时，执行用时358ms，371ms,364ms,试验了几次都不一样，内存124.63，124.64,124.70MB
写if(k>1)时，执行用时343ms,350ms,359ms内存124.56MB,124.63MB,124.67MB
gpt是对的，真的更节省，有微妙的区别。但区别也不大

            */
        }
        return count;
    }
};