C++ Solution, with explanations


  • 0
    J

    The idea here to iterate each point, get the number of points that have same distance to this one. However, this means the distance between any two different points will be calculated twice. I hadn't found a way to optimize it.
    Anyone has an idea to make it work if distance is only calculated once?

    class Solution {
    public:
        int numberOfBoomerangs(vector<pair<int, int>>& points) {
            int n=points.size(), res=0, dist, dx, dy;
            for (int i=0; i<n; ++i){
                // make a map for each point
                unordered_map<int,int> mp;
                for (int j=0; j<n; ++j){
                    if(j==i) continue;
                    // calculate the square of the distance
                    dx=(points[i].first - points[j].first);
                    dy=(points[i].second - points[j].second);
                    mp[dx*dx+dy*dy]++;
                }
                for (auto it=mp.begin(); it!=mp.end(); it++){
                    // get the purmutation number from points with same distance to current one
                    res += it->second * (it->second-1); 
                }
            }
            return res;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.