C++ solution time:O(n^2*log(n)) 526ms


  • 0
    K
    class Solution {
    public:
        int numberOfBoomerangs(vector<pair<int, int>>& points) {
            int res=0;
            for(int i=0;i<points.size();++i)
            {
                vector<int>d;
                for(int j=0;j<points.size();++j)
                    d.push_back((points[i].first-points[j].first)*(points[i].first-points[j].first)+(points[i].second-points[j].second)*(points[i].second-points[j].second));
                sort(d.begin(),d.end());
                int cnt=1;
                for(int j=1;j<d.size();++j)
                    if(d[j]==d[j-1])
                        cnt++;
                    else
                    {
                        res+=cnt*(cnt-1);
                        cnt=1;
                    }
                res+=cnt*(cnt-1);
            }
            return res;
        }
    };

  • 0
    M
    This post is deleted!

  • 0
    K

    @myway yes.It's O(n*(n+nlgn))=O(n^2lgn). as n*(n+n*lgn)=(1+lgn)*n^2


  • 0
    M

    @kupe yeah, apparently it is. not clear mind before. thx.


Log in to reply
 

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