Does anybody know better solution than O(n^2) solutions?


  • 1

    A brute force O(n^2) solution.

    const int INF = 0x3f3f3f3f;
    class Solution {
     private:
      double getSlope(Point& p1, Point& p2) {
        if (p1.x == p2.x)
          return INF;
        else
          return (double)(p1.y - p2.y) / (p1.x - p2.x);
      }
    
     public:
      int maxPoints(vector<Point>& points) {
        if (points.size() < 3) return points.size();
        int maxn = 0, size = points.size();
    
        map<double, int> cnt;
        for (int i = 0; i < size - 1; i++) {
          cnt.clear();
          int same = 1, curmax = 0;
    
          for (int j = i + 1; j < size; j++)
            if (points[i].x == points[j].x && points[i].y == points[j].y)
              same++;
            else {
              double slope = getSlope(points[i], points[j]);
              cnt[slope]++;
              curmax = max(curmax, cnt[slope]);
            }
    
          maxn = max(maxn, curmax + same);
        }
    
        return maxn;
      }
    };
    

Log in to reply
 

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