C++ 8ms solution, beaten 100%


  • 0
     int compare(const void *a, const void *b)
     {
         if (*(float*)a<*(float*)b) return -1;
         if (*(float*)a>*(float*)b) return 1;
         return 0;
     }
    
    class Solution {
    public:
    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.
         int N = points.size();
         if (N<2)
             return N;
         float slope[N][N];
         for (int i=0;i<N;i++)
         {
             slope[i][i]=-999999;
             for (int j=i+1;j<N;j++)
             {
                 if (points[i].x!=points[j].x)
                     slope[i][j] = float(points[i].y-points[j].y)/float(points[i].x-points[j].x);
                 else if(points[i].y!=points[j].y)
                     slope[i][j] = 999999;
                 else
                     slope[i][j] = -999999;
    
                 slope[j][i] = slope[i][j];
             }
         }
         int MAX = 1,current_len;
         float temp;
         for (int i=0;i<N;i++)
         {
             qsort(slope[i],N,sizeof(float),compare);
             int j=0,same = 0;
             while (slope[i][j]==-999999 && j<N-1)
             {
                 same++;
                 j++;
             }
             current_len = same;
             if (j<N)
             {
            	 current_len++;
            	 temp = slope[i][j];
            	 j++;
             }
             if (current_len>MAX)
            	 MAX = current_len;
             for (;j<N;j++)
             {
                 if (slope[i][j]-temp<0.0001 && slope[i][j]-temp>-0.0001)
                 {
                     current_len++;
                     if (current_len>MAX)
                         MAX = current_len;
                 }
                 else
                 {
                     temp = slope[i][j];
                     current_len=same+1;
                 }
             }
         }
         return MAX;
     }
    };

  • 0
    O

    The popular solution is to use a hash to take records of slopes and it's O(n^2).
    Roughly speaking,

    1. Generates slopes array for each point. Each point has O(n) slopes.
    2. For each node's slopes, you qsort them O(n)O(nlogn)
      You have O(n^2
      logn) time complexity and you are the fastest. Strange.

  • 0
    Q

    I think there are two reasons:

    1. His code is actually more like C
    2. HashMap is actually not as fast as we think. There are a lot of overhead, and the effect becomes more apparent when N is not that big.

Log in to reply
 

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