2015年10月15日星期四

Leetcode 149 Max Points on a Line

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
Solution 1: Method is brute force, but use 2 layer of Hash table to store the slop (dy/dx) and deal with the corn case.
 public class Solution {  
   public int maxPoints(Point[] points) {  
     int n=points.length;  
     Map<Integer,Map<Integer,Integer>> map=new HashMap<>();  
     int res=0;  
     for (int i=0; i<n; i++) {  
       map.clear();  
       int overlap=0, max=0;  
       for (int j=i+1; j<n; j++) {  
         int x=points[j].x-points[i].x;  
         int y=points[j].y-points[i].y;  
         if (x==0) {  
           if (y==0) {  
             overlap++;  
             continue;  
           }  
           else y=1;  
         }  
         else if (y==0) x=1;  
         else {  
           int gcd=calGcd(x,y);  
           x=x/gcd;  
           y=y/gcd;  
         }  
         int count=1;  
         if (!map.containsKey(x)) {  
           Map<Integer,Integer> one=new HashMap<>();  
           one.put(y,1);  
           map.put(x,one);  
         }  
         else if (!map.get(x).containsKey(y)) {  
           map.get(x).put(y,1);  
         }  
         else {  
           count=map.get(x).get(y);  
           map.get(x).put(y,++count);  
         }  
         max=Math.max(max,count);  
       }  
       res=Math.max(res,max+overlap+1);  
     }  
     return res;  
   }  
   private int calGcd(int x, int y) {  
     while (y!=0) {  
       int temp=y;  
       y=x%y;  
       x=temp;  
     }  
     return x;  
   }  
 }  

没有评论:

发表评论