Accepted O(n^2) simple solution


  • 1
    P

    Principles:

    1, from each ith point, find all lines passing it and choose the one with maximum points in (i, n]. this number is notated as max_i

    2, pick the maximum value from {max_i} and return.

    tricky part:

    1, for each ith point, we only need to compare it and elements (i, n].

    2, ways of solving repeating elements

    code:

    class Solution{
    public:
    int maxPoints(vector< Point> &points)
    {
    int n = points.size();
    //points.size is smaller than 3
    if (n < 3)
    return n;

        //general case
        int res = 0;
    
        for (int i = 0; i < n; i++)
        {      // all line will pass through ith element 
            int ni(1), max_count(0); //ni is the number of repeating point for ith
            map<double, int> count;  //count the number of points for each line (determined by slope)
            for (int j = i + 1; j < n; j++)
            {
                if (points[i].x == points[j].x)
                { 
                    if (points[i].y == points[j].y)   //same point
                        ni++;
                    else //vertical
                        count[INT_MAX - INT_MIN + 1] += 1;
                }
                else
                    count[double(points[i].y - points[j].y) / (points[i].x - points[j].x)] += 1;
            }
            for (map<double, int>::iterator it = count.begin(); it != count.end(); it++)
                max_count = (max_count < (it->second)) ? (it->second) : max_count;
    
            max_count += ni;
            res = (res < max_count) ? max_count : res;
        }
    
        return res;
    }
    

    };


  • 0
    T
    This post is deleted!

  • 0
    L

    original comment

    never mind, get in wrong


  • 0
    B

    It may not be a correct solution, because slopes can vary due to round-off errors.

    say, (0,0) (1,100000000000) and (2,200000000001) can be on the same line, but they are not.

    count[double(points[i].y - points[j].y) / (points[i].x - points[j].x)] += 1;


  • 0
    P

    because x and y are int type, they can't be as big as 100000000000.
    if you make it that big, then I can change double to long double


  • 0
    B

    I am not saying about the range of doubles, of course, doubles can work with 1E+- 308. But it only preserves up to an accuracy, which can not keep more than 15 valid digits. On the other hand, possible slopes can exceed that number. It would be nice to customize a slope key class to work around this problem.


Log in to reply
 

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