A Simple Java Solution


  • 0
    Y

    Sort the points array. Then first compute the maximum points on one line for the first point: count the duplicate points with the first point in variable dup; then the first point and the slope determine one line. Maintain a HashMap which maps slope to number of points on this line. Keep the max numbers.

    public int maxPoints(Point[] points) {
            if(points == null || points.length < 3){
                return points.length;
            }
            Arrays.sort(points, new Comparator<Point>(){
                @Override
                public int compare(Point o1, Point o2) {
                    if(o1.x != o2.x){
                        return o1.x - o2.x;
                    }
                    return o1.y - o2.y;
                }
            });
            int result = 0;
            for(int i = 0 ; i < points.length; i ++){
                if(i == 0 || !samePoint(points[i], points[i - 1])){
                    Map<Double, Integer> map = new HashMap<>();
                    int dup = 0;
                    int tmpMax = 1;
                    for(int j = i + 1; j < points.length ; j ++){
                        if(samePoint(points[j], points[i])){
                            dup ++;
                        }else{
                            double slope = points[j].x == points[i].x ? Integer.MAX_VALUE : (points[j].y - points[i].y) * 1.0 / (points[j].x - points[i].x);
                            map.put(slope, map.containsKey(slope) ? map.get(slope) + 1 : 2);
                            tmpMax = Math.max(tmpMax, map.get(slope));
                        }
                        result = Math.max(result, dup + tmpMax);
                    }
    
                }
            }
            return result;
        }
    
        private boolean samePoint(Point p1, Point p2){
            return p1.x == p2.x && p1.y == p2.y;
        }
    

Log in to reply
 

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