16ms c++ easy understanding solution


  • 6
    S
    class Solution {
    public:
        int maxPoints(vector<Point>& points) {
            int n = (int)points.size();
            unordered_map<float, int> map;
            int res = 0;
            for(int i = 0; i < n; i++){
                int same = 1;
                int vertical = 0;
                int tmp = 0;
                map.clear();
                for(int j = i + 1; j < n; j++){
                    Point a = points[i];
                    Point b = points[j];
                    if(a.x == b.x){
                        if(a.y != b.y){
                            vertical++;
                        }
                        else{
                            same++;
                        }
                    }
                    else{
                         tmp = max(++map[(float)(b.y - a.y) / (b.x - a.x)], tmp);
                    }
                }
                res = max(res, same + max(vertical, tmp));
            }
            return res;
        }
    };

  • 1

    I think it would be better if you put this line "Point a = points[i];" out of the second "for" loop.(I am sorry for my poor English!)


  • 2

    Solution fails below test. It's unsafe to use float/double as keys.

    Submission Result:  Wrong Answer
    Input: [[0,0],[94911151,94911150],[94911152,94911151]]
    Output: 3
    Expected: 2
    

    One possible solution is to encode slopes as strings

    int rise = p2.y - p1.y;
    int run  = p2.x - p1.x;
    int g = gcd(rise, run);
    string slope = to_string(rise/g) + "," + to_string(run/g);
    

  • 0
    T

    @sys you can use long double


Log in to reply
 

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