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日星期日