My Solution Without nested map in C++


  • 1
    R

    One key point is to convert the slope and intercept into a long long type.

     /*
         *  A line is determined by two factors,say y=ax+b
         *  
         *  If two points(x1,y1) (x2,y2) are on the same line(Of course). 
    
         *  Consider the gap between two points.
    
         *  We have (y2-y1)=a(x2-x1),a=(y2-y1)/(x2-x1) a is a rational, b is canceled since b is a constant
    
         *  If a third point (x3,y3) are on the same line. So we must have y3=ax3+b
    
         *  Thus,(y3-y1)/(x3-x1)=(y2-y1)/(x2-x1)=a
    
         *  Since a is a rational, there exists y0 and x0, y0/x0=(y3-y1)/(x3-x1)=(y2-y1)/(x2-x1)=a
    
         *  So we can use y0&x0 to track a line;
         
         *  In my code, 'x' and 'y' stands for x0 and y0 mentioned above.
    
         *  I convert them into a long long type for hash purpose.
    
         */
    
        class Solution{
        public:
        	int maxPoints(vector<Point> &points){
        		if (points.size()<=2) return points.size();
        
        		std::unordered_map<long long,int> map;
        		int result=0,localmax,overlap,x,y,gcd,curr;
                long long key;
                
        		for (unsigned int i=0,size=points.size();i<size;i++){
        		    if (result>=size-i) break;
        			map.clear();
        			localmax=0,overlap=0;
        			for (unsigned int j=i+1;j<size;j++){
        				x=points[j].x-points[i].x;
        				y=points[j].y-points[i].y;
        				//check overlap
        				if ((x==0)&&(y==0)){
        					overlap++;
        					continue;
        				}
        				gcd=generateGCD(x,y);
        				x/=gcd; y/=gcd;
        				//Calculate the key by shifting left 'x' 32 bits, and then add 'y' 
        				key=0L;key+=x;key<<=32;key+=y;
        				//find x,then y;
        				int curr=++map[key];
        				localmax=max(curr,localmax);
        			}
        			result=max(result,localmax+overlap+1);
        		}
        		return result;
        	}
        private:
        	int generateGCD(int a, int b){
        		if (b==0) return a;
        
        		return generateGCD(b,a%b);
        
        	}
        };

Log in to reply
 

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