【每日一题】回旋镖的数量

Tag

【组合数学】【数组】【2024-01-08】

---

题目来源

447. 回旋镖的数量

---

解题思路

方法一：组合数学

思路

以数组 points 中的每一个为回旋镖的中心 i，在数组 points 中找距离中心 i 相等的一对点，于是可以先试用一个哈希表来记录到中心 i 的不同距离的个数，再在这些不同距离的个数中取出两个元素，与中心 i 构成回旋镖的位置。

算法

class Solution {
public:
    int numberOfBoomerangs(vector<vector<int>>& points) {
        int res = 0;
        for (auto &p : points) {
            unordered_map<int, int> cnts;
            for (auto &q : points) {
                int dis = (p[0] - q[0]) * (p[0] - q[0]) + (p[1] - q[1]) *(p[1] - q[1]);
                ++cnts[dis];
            }
            for (auto&[_, m] : cnts) {
                res += m * (m-1);
            }
        }
        return res;
    }
};

复杂度分析

时间复杂度：$O(n^2)$，$n$ 为数组 points 的长度。

空间复杂度：$O(n)$。

---

写在最后

如果您发现文章有任何错误或者对文章有任何疑问，欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度的方法，欢迎评论区交流。

最后，感谢您的阅读，如果有所收获的话可以给我点一个 👍 哦。