A clean java O(n^2) solution with annotation


  • 0
    T

    public class Solution {

    class Line{
    	//slope is null iff it's vertical
    	//if line is not vertical, intersect is y-intersection
    	//if line is vertical, intersect is x-intersection
    	Double slope; Double intersect;
    	//some pseudo-pseudo random number
    	static final int rand=65536123;
    	
    	//clean constructor interface
    	Line (double slope,double intersect){
    		this.slope=slope; 
    		this.intersect=intersect;
    	}
    	
    	//precondition: alpha and beta not same point
    	Line (Point alpha,Point beta){
    		if (alpha.x==beta.x){
    			this.slope=null;
    			this.intersect=(double)alpha.x;
    		}
    		else {
    			this.slope=(double)((alpha.y-beta.y)/((double)(alpha.x-beta.x)));
    			this.intersect=(beta.y*alpha.x-alpha.y*beta.x)/((double)alpha.x-beta.x);
    		}
    	}
    	
    	@Override
    	public boolean equals(Object beta){
    		boolean output=false;
    		if (beta instanceof Line){
    			Line betaLine=(Line) beta;
    			return ((this.slope==null && betaLine.slope==null)||approxEqual(this.slope,betaLine.slope))&&approxEqual(this.intersect,betaLine.intersect);
    		}
    		return output;
    	}
    	
    	@Override
    	public int hashCode(){
    			final int prime = 31; 
    			int result = 1; 
    			result = prime * result + (this.slope==null?rand:this.slope.hashCode()); 
    			result = prime * result + (this.intersect==null?rand:this.intersect.hashCode()); 
    			return result;
    	}
    	
    	public String toString(){
    		String output="";
    		output+="slope: "+(this.slope==null?"null":this.slope)+"intersect: "+(this.intersect==null?"null":this.intersect);
    		return output;
    	}
    }
    
    public boolean approxEqual(double a,double b){
    	return Math.abs(a-b)<0.0001;
    }
    
    //O(n^2) algo
    public int maxPoints(Point[] points) {
    	//case defense: there is always a line when only one point
    	if (points==null || points.length==0) return 0;
    	if (points.length==1) return 1;
    	//key: Line; Value: the count of points in this line
        HashMap<Line,HashSet<Point>> H=new HashMap<Line,HashSet<Point>>();
        
        for (int i=1;i<points.length;i++){
        	Point iPoint=points[i];
        	for (int j=0;j<i;j++){
        		Point jPoint=points[j];
        		Line Line_IJ=new Line(iPoint,jPoint);  
        		//if two same points, let the line be null
        		if (approxEqual(iPoint.x,jPoint.x)&& approxEqual(iPoint.y,jPoint.y))  Line_IJ=null;
        		
        		//if H does not contain Line_IJ, just put (Line_IJ) into H, add iPoint & jPoint into Line_IJ's pointSet
        		if (Line_IJ!=null && (!H.keySet().contains(Line_IJ))){
        			HashSet<Point> pointSet=new HashSet<Point>();
        			H.put(Line_IJ, pointSet);
        		}
        		//if H does contain Line_IJ, corresponding pointSet of Line_IJ
        		//if pointSet does not iPoint/jPoint, add iPoint/jPoint to pointSet, 
        		else if (Line_IJ!=null){
        			HashSet<Point> pointSet=H.get(Line_IJ);
        		}
        		
        	}
        }
        //now we have all the lines, we want to fit points on the lines
        
        //another defense
        if (H.size()==0){
        	HashSet<Point> pointSet=new HashSet<Point>();
        	H.put(new Line(points[0],points[1]),pointSet);
        }
        
        //sweep on the lines on all the points to see if it fits, if fit, add to corresponding HashSet
        for (Point p:points){
        	for (Line L:H.keySet()){
        		//L is vertical?
        		if (L.slope==null){
        			if (approxEqual(p.x,L.intersect)){H.get(L).add(p);}
        		}
        		else {
        			if (approxEqual(L.slope*p.x+L.intersect,p.y)){H.get(L).add(p);}
        		}
        	}
        }
        
        int output=0;
        for (Line L:H.keySet()){
        	if (H.get(L).size()>output) output=H.get(L).size();
        }
        return output;
    }
    

    }


Log in to reply
 

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