Leetcode——447. Number of Boomerangs

本文主要是介绍Leetcode——447. Number of Boomerangs，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

最近写文章总想用英语来写，但是自己的英语又poor，写的又慢，没办法，只能中英mixed着吧！
我真不是装B，我是真的想practice My English!

Problem

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

solution

注意：[i,j,k]和[i,k,j]是两个！
解决方案：就是遍历1到n，假设遍历到i，然后寻找i到其他所有非i的数距离，并把相同的距离个数记录。如果对于某一个距离，只有一个，那么就不会有tuple，如果某个距离，有k个，则相应的tuple为k*(k-1)，然后把所有的tuple个数相加就可得到总的tuple组数。

为了存储方便，可以用unordered_map。
总的时间复杂度为O(N^2)！

class Solution {//unordered_map
public:int numberOfBoomerangs(vector<pair<int, int>>& points) {if(points.size()<3) return 0;int res=0;for(int i=0;i<points.size();i++){unordered_map<int,int> m;//key：distance，value：the number of the distancefor(int j=0;j<points.size();j++){if(i==j) continue;int dis=distance(points[i],points[j]);m[dis]++;}unordered_map<int,int>::iterator itr;for(itr=m.begin();itr!=m.end();itr++){res=res+itr->second*(itr->second-1);}}return res;}
private:int distance(pair<int,int>a,pair<int,int>b){int res;res=(a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second);return res;}
};