LeetCode——Number of Boomerangs

Question

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

解题思路

注意这道题只需要求有多少对，没有具体要求是哪些，所以可以只记录点之间的距离。可以考虑用一个hash table记录每一个点到其他所有点的距离，如果相同距离数目大于等于2，那么必有满足要求的组合。就是最后的时候注意如何求这样的组合。假如距离为6的点对是a，那么这样的对数就是： (a * (a - 1) / 2) * 2.

具体实现

#include <iostream>

#include <vector>

#include <map>

using namespace std;

class Solution {

public:

    int numberOfBoomerangs(vector<pair<int, int>>& points) {

        int res = 0;

        for (int i = 0; i < points.size(); i++) {

            map<int, int> dis_map;

            for (int j = 0; j < points.size(); j++) {

                if (i != j) {

                    int dis = distance(points[i], points[j]);

                    dis_map[dis]++;

                }

            }

            for (map<int, int>::iterator it = dis_map.begin(); it != dis_map.end(); it++) {

                res += (it->second * (it->second - 1) / 2) * 2;

            }

        }

        return res;

    }

    int distance(pair<int, int>& a, pair<int, int>& b) {

        int x = (a.first - b.first) * (a.first - b.first);

        int y = (a.second - b.second) * (a.second - b.second);

        return x + y;

    }

};

巴特西

LeetCode——Number of Boomerangs