Two force method of C++ 24ms to solve this question


  • 0
    J
     int maxPoints1(vector<Point> &points) {
        int n=points.size();
        if (n < 3) 
            return n;
        int result = 0;
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                int sign = 0;
                int a, b, c;
                if (points[i].x == points[j].x) 
                    sign = 1;
                else {
                    a = points[j].x - points[i].x;
                    b = points[j].y - points[i].y;
                    c = a * points[i].y - b * points[i].x;
                }
                int count = 0;
                for (int k = 0; k < n; k++) {
                    if ((0 == sign && a * points[k].y == c + b * points[k].x) ||
                            (1 == sign&&points[k].x == points[j].x))
                        count++;
                }
                if (count > result) 
                    result = count;
            }
        }
        return result;
    }
    
    int maxPoints(vector<Point> &points) {
        int n=points.size();
        if (n < 3) 
            return n;
        int result=0;
        unordered_map<double,int> number;
        for(int i=0;i<n-1;++i){
            number.clear();
            int samePoint=0;
            int local_max=1;//和i共线
            for(int j=i+1;j<n;++j){
                double slope;//斜率
                if(points[i].x==points[j].x){
                    slope = std::numeric_limits<double>::infinity();
                    if(points[i].y==points[j].y){
                        ++samePoint;
                        continue;
                    }
                }else{
                    slope = 1.0 * (points[i].y - points[j].y) /(points[i].x - points[j].x);
                }
                int count=0;
                if(number.find(slope)!=number.end()){
                    count = ++number[slope];
                }else{
                    count=2;
                    number[slope]=count;
                }
                if(local_max<count)
                    local_max=count;
            }
            result = max(result,local_max+samePoint);
        }
        return result;
    }

Log in to reply
 

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