My C++ solution without using hash table and accepted


  • 0
    B
    class compare_points {
    public:
        bool operator()(const Point& p1, const Point& p2) {
            if (p1.x < p2.x)
                return true;
            else if (p1.x == p2.x && p1.y < p2.y)
                return true;
            return false;
        }
    };
    class Solution {
        bool isOneLine(const Point& p1, const Point& p2, const Point& p3) {
            if ((p2.y - p1.y)*(p3.x - p1.x) == (p3.y - p1.y)*(p2.x - p1.x)) {
                if ((p2.y - p1.y) == 0 && (p3.y - p1.y) == 0)
                    return true;
                if ((p3.x - p1.x) == 0 && (p2.x - p1.x) == 0)
                    return true;
                if ((p2.y - p1.y) != 0 && (p3.y - p1.y) != 0 &&
                    (p3.x - p1.x) != 0 && (p2.x - p1.x) != 0)
                    return true;
            }
            return false;
        }
        bool equalPoint(const Point& p1, const Point& p2) {
            return p1.x == p2.x && p1.y == p2.y;
        }
    
    public:
        int maxPoints(vector<Point>& points) {
            if (points.size() < 3)
                return points.size();
    
            sort(points.begin(), points.end(), compare_points());
            int maxPoint = -1;
            for (int i = 0; i < points.size()-2; ++i) {
                int samePointCount = 0;
                for (int j = i+1; j < points.size()-1; ++j) {
                    if (equalPoint(points[i], points[j])) {
                        samePointCount ++;
                        continue;
                    }
    
                    int current_point_numbers = 2;
                    for (int k = j+1; k < points.size(); ++k) {
                        if (isOneLine(points[i], points[j], points[k])) {
                            current_point_numbers ++;
                        }
                    }
                    current_point_numbers += samePointCount;
                    if (current_point_numbers > maxPoint) {
                        maxPoint = current_point_numbers;
                    }
                }
            }
            if (maxPoint == -1) {
                return points.size();
            }
            maxPoint = maxPoint > points.size() ? points.size() : maxPoint;
            return maxPoint;
        }
    };
    

  • 0

    So the trade-off here is to use O(n^3)time in exchange of O(1)space usage, right?


Log in to reply
 

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