Wrong answer with a O(n^2) algorithm


  • 1
    Z
    /**
     * Definition for a point.
     * struct Point {
     *     int x;
     *     int y;
     *     Point() : x(0), y(0) {}
     *     Point(int a, int b) : x(a), y(b) {}
     * };
     */
    class Solution {
    public:
        int max(int a, int b) {
            return a > b ? a : b;
        }
    
        int maxPoints(vector<Point> &points) {
            // IMPORTANT: Please reset any member data you declared, as
            // the same Solution instance will be reused for each test case.
            if(points.size() == 0)
                return 0;
            if(points.size() == 1)
                return 1;
            unordered_map<double, int> slope_count;
            int res;
            for(int i = 0; i < points.size(); ++i) {
                slope_count.clear();
                int overlapPoints = 0;//number of points which are overlap with current point
                int infinitySlope = 0;//number of points which are in the vertical line with current point
                for(int j = i + 1; j < points.size(); ++j) {
                    if(points[i].x == points[j].x) {
                        if(points[i].y == points[j].y) {
                            overlapPoints++;
                        } else {
                            infinitySlope++;
                        }
                    } else {
                        double slope = (points[i].y - points[j].y) / (points[i].x - points[j].x);
                        slope_count[slope]++;
                    }
                }
                res = max(res, infinitySlope + overlapPoints + 1);
                for(auto ite = slope_count.begin(); ite != slope_count.end(); ite++) {
                    res = max(res, ite->second + overlapPoints + 1);
                }
            }
            return res;
        }
    };
    

    Input: [(84,250),(0,0),(1,0),(0,-70),(0,-70),(1,-1),(21,10),(42,90),(-42,-230)]

    Output: 8

    Expected: 6

    The thought of this algorithm is useing a map to store the number of points(value) that share a same slope(key). But it gets a wrong answer. Why?


  • 3
    S

    The key point of this problem is how to design hash key value for the slope. Apparently you just use double as key without handing its precision. It will lead wrong answer.


  • 0
    Z

    Oh yeah! You reminder me. But In fact, double is enough. The problem is "double slope = (points[i].y - points[j].y) / (points[i].x - points[j].x);". I change it to "double slope = 1.0 * (points[i].y - points[j].y) / (points[i].x - points[j].x);". Then it works! Thank you!


Log in to reply
 

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