C++ solution for Max Points on a line(beat 92.01%) O(n2)


  • 0
    G
    class Solution {
    public:
        int maxPoints(vector<Point>& points) {
            int result=0;
            if(points.size()<=2)return points.size();
            unordered_map<double,int> mp;
            for(int i=0;i<points.size()-1;i++){
                int x1=points[i].x;
                int y1=points[i].y;
                int sameP=0;
                int sameX=0;
                int localMax=0;
                for(int j=i+1;j<points.size();j++){
                    int x2=points[j].x;
                    int y2=points[j].y;
                    if(x1==x2&&y1==y2){sameP++;continue;}
                    if(x1==x2){sameX++;continue;}
                    double slope=(double)(y2-y1)/(double)(x2-x1);
                    localMax=max(++mp[slope],localMax);
                }
                result=max(result,localMax+sameP);
                result=max(result,sameX+sameP);
                mp.clear();
            }
            return result+1;
        }
    };

Log in to reply
 

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