LeetCode Number of Boomerangs

LeetCode Number of Boomerangs

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

给定一堆点集,问回飞镖的个数。一个回飞镖是一个三点集(i,j,k),且满足i到j和k的距离相等。

如果和i距离相等的点有n个,则这样的三点集有A_n^2=n(n-1),也就是从n个点中拿两个点做排列。所以问题就转换为对每个点,都求其他所有点和该点的距离,求到距离相等的点的个数n,然后代入公式计算。

代码如下:

class Solution {
public:
	int numberOfBoomerangs(vector<pair<int, int>>& points) {
		int ans = 0;
		for (int i = 0; i < points.size(); ++i) {
			unordered_map<int, int> dist_cnt;
			for (int j = 0; j < points.size(); ++j) {
				int xdiff = points[i].first - points[j].first;
				int ydiff = points[i].second - points[j].second;
				++dist_cnt[xdiff*xdiff + ydiff*ydiff];
			}
			for (auto it = dist_cnt.begin(); it != dist_cnt.end(); ++it)ans += it->second*(it->second - 1);
		}
		return ans;
	}
};

本代码提交AC,用时369MS。

因为题中说到所有点都是不相同的,所以第7行没必要限制j!=i,即使j==i,算出来的距离是0,dist_cnt[0]=1,也就是只有点x一个点和自己的距离是0。到第12行计算排列数时,n(n-1)=0,所以没关系。

Leave a Reply

Your email address will not be published. Required fields are marked *