My 9ms o(n^2) C++ solution.


  • 0
    M
    bool comp(Point& a,Point& b){
        return a.x<b.x||(a.x==b.x&&a.y<b.y);
    }
    class Solution {
    private:    
        bool isSame(Point& a,Point& b){
            return a.x==b.x&&a.y==b.y;
        }
        double getSlope(Point& a,Point& b){
            return ((double)b.y-a.y)/(b.x-a.x);
        }
    public:
        int maxPoints(vector<Point>& points) {
            if(points.size()<3)return points.size();
            int end=points.size()-2,ans=2;
            unordered_map<double,int> count;
            sort(points.begin(),points.end(),comp);
            for(int i=0;i<end;++i){
                int same=1,maxp=0;
                count.clear();
                while(i<points.size()&&isSame(points[i],points[i+1])) ++i,++same;
                int j=i+1;
                while(j<points.size()&&points[i].x==points[j].x) ++j,++maxp;
                for(;j<points.size();++j){
                    double slope=getSlope(points[i],points[j]);
                    maxp=max(maxp,++count[slope]);
                }
                ans=max(ans,maxp+same);
                end=points.size()-ans;
            }
            return ans;
        }
    };

Log in to reply
 

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