149. Max Points on a Line

系统管理员 2021-12-22 06:55 289阅读 0赞

class Solution {
    public int maxPoints(Point[] points) {
        if(points.length<3)
            return points.length;
        int res=0;
        Map<Integer, Map<Integer,Integer>> map=new HashMap<Integer, Map<Integer, Integer>>();
        for(int i=0;i<points.length;i++)
        {
            map.clear();
            int samepoint=1,max=0;
            for(int j=i+1;j<points.length;j++)
            {
                int x=points[i].x-points[j].x;
                int y=points[i].y-points[j].y;
                if(x==0&&y==0)
                    samepoint++;
                else
                {
                    int d=gcd(x,y);
                    x/=d;
                    y/=d;
                    if (map.containsKey(x)){
                        if (map.get(x).containsKey(y)){
                            map.get(x).put(y, map.get(x).get(y)+1);
                        }else{
                            map.get(x).put(y, 1);
                        }                       
                    }else{
                        Map<Integer,Integer> m = new HashMap<Integer,Integer>();
                        m.put(y, 1);
                        map.put(x, m);
                    }
                    max=Math.max(max, map.get(x).get(y));                    
                }
                res=Math.max(max+samepoint,res);
            }
        }
        return res;
    }
    private int gcd(int a, int b){
        if(b==0)
            return a;
        return gcd(b, a%b);
    }
}