Thursday, December 25, 2014

Max Points on a Line (LeetCode HashMap)

Question: Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

Idea: Brute force. For each point i, construct lines with all the other points. The other points may be at the same place, or vertical (slope=+Infinite) or horizontal (slope=+0). Since the lines are constructed from point i, once the slope of line (i->j) is the same as a line constructed before, j is on a line constructed before. When calculating the slope, take care 0.0!=-0.0==0.0/-1 in Java.

Time: O(n^2) Space:O(n)

Code: 
 public class Solution {  
   public int maxPoints(Point[] points) {  
     if(points.length==0)  
     {  
       return 0;  
     }  
     HashMap<Double,Integer> counter=new HashMap<Double,Integer>();  
     int result=1;  
     for(int i=0;i<points.length;i++)  
     {  
       counter.clear();  
       counter.put((double)Integer.MAX_VALUE,1);  
       int dup=0;  
       for(int j=i+1;j<points.length;j++)  
       {  
         if(points[i].x==points[j].x&&points[i].y==points[j].y)  
         {  
           dup+=1;  
           continue;  
         }  
         double slope=(points[i].x==points[j].x)?Integer.MAX_VALUE:0.0+(0.0+points[i].y-points[j].y)/(0.0+points[i].x-points[j].x);  
         if(counter.containsKey(slope))  
         {  
           counter.put(slope,counter.get(slope)+1);  
         }  
         else  
         {  
           counter.put(slope,2);  
         }  
       }  
       for(int number:counter.values())  
       {  
         result=Math.max(result,number+dup);  
       }  
     }  
     return result;  
   }  
 }  

No comments:

Post a Comment