MENU

LeetCode447. Number of Boomerangs(模拟)

2019 年 02 月 17 日 • 阅读: 820 • LeetCode阅读设置

LeetCode447. Number of Boomerangs(模拟)

  • Easy
  • Accepted:50,055
  • Submissions:102,203

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]]

链接

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

题意

给定平面上的n个点,找到所有由这些点构成的三元组(i, j, k)数量,三元组(i, j, k)满足i,j两点的距离等于i,k两点的距离。n在500以内,点的坐标范围为[-10000, 10000]

题解

  • 三重暴力循环找三个点,时间复杂度$O(n^3)​$
  • 因为求的是i点到其余两点距离相等,所以我们可以把i点看做“中心点”,对于每一个点i,求其到其余点的距离,把距离和该距离出现的次数cnt建立键值对关系,放入查找表中,如果cnt大于1,那么对于该点的答案为$cnt * (cnt-1)$ ,最后再累加即可,时间复杂度为$O(n^2)​$

代码

  • Runtime: 568 ms, faster than 72.22% of C++ online submissions for Number of Boomerangs.
  • Memory Usage: 133.6 MB, less than 100.00% of C++ online submissions for Number of Boomerangs.
class Solution {
public:
    int dis(pair<int, int> &pa, pair<int, int> pb) // 防止小数使用距离平方
    {
        return (pa.first - pb.first) * (pa.first - pb.first) +
                (pa.second - pb.second) * (pa.second - pb.second);
    }

    int numberOfBoomerangs(vector<pair<int, int>>& points) {
        int ans = 0;
        for (int i = 0; i < points.size(); ++i)
        {
            unordered_map<int, int> umap;
            for (int j = 0; j < points.size(); ++j)
                if (j != i)
                    umap[dis(points[i], points[j])]++; // “距离相同的点”
            for (auto it : umap)
            {
                if (it.second > 1)
                    ans += it.second * (it.second - 1);
            }
        }
        return ans;
    }
};

The end.
2019年2月17日 星期日