My cpp solution in 16ms


  • 0
    L

    For each point, calculate slops that between it and all others points and use a hash map to store them like

    unordered_map<double,int> map;   //slop, amount 
    

    I use float to represent slop so the vertical lines need to be taken care as corner case. For one point, if other overlap points are found, just hold their amount, and add it to max point line that from this point


        class Solution {
        public:
            int maxPoints(vector<Point>& points) {
                if(points.empty())return 0;
                unordered_map<double,int> map;   //slop, amount
                double slope;
                inclass Solution {
    public:
        int maxPoints(vector<Point>& points) {
            if(points.empty())return 0;
            unordered_map<double,int> map; 
            double slope;
            int maxp=1,maxp_temp=1,dup=0;
            for(int i=0;i<points.size();i++){
                for(int j=i+1;j<points.size();j++){
                    if(points[i].x==points[j].x&&points[i].y==points[j].y){
                        dup++;
                        continue;
                    }
                    if(points[i].x==points[j].x){
                        maxp_temp=max((++map[NULL])+1,maxp_temp);
                        continue;
                    }
                    slope =(double(points[i].y-points[j].y)/(points[i].x-points[j].x));
                    maxp_temp=max((++map[slope])+1,maxp_temp);
                }
                maxp_temp+=dup;
                maxp=max(maxp,maxp_temp);
                maxp_temp=1;
                dup=0;
                map.clear();
            }
            return maxp;
        }
    };

Log in to reply
 

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