11ms java solution without any map structure


  • 5
    L
         public int maxPoints(Point[] points){
      if(points == null || points.length == 0){
          return 0;
      }
      
      if(points.length <= 2){
          return points.length;
      }
      
      int ret = 0;
      
      int n = points.length;
      int count = 0; 
      int duplicates = 0;
      
      for(int i = 0; i < n; i++){
          Point p = points[i];
          count = 0;
          duplicates = 0;
          
          for(int j = i + 1; j < n; j++){
              Point q = points[j];
              if(q.x == p.x && q.y == p.y){
                  duplicates++;
                  ret = Math.max(ret, duplicates + 1);
                  continue;
              }
              
              //count point q
              count = 1;
              
              for(int k = j + 1; k < n; k++){
                  Point r = points[k];
                  count += isCoLinear(p, q, r)? 1: 0;
              }
              
              //count point p
              ret = Math.max(ret, count + duplicates + 1);
          }
          
      }
      
      return ret;
    

    }

     private boolean isCoLinear(Point p, Point q, Point r){
      int val = (q.y - p.y) *(r.x - q.x) - (r.y - q.y)*(q.x - p.x);
      return val == 0;
    

    }


  • 0
    Y

    @larrywang2014
    use map structure is O(n^2), your sollution is O(n^3).
    It is a good try.


Log in to reply
 

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