Java, O(n^2) solution, calc the "a" & "b" in "y=a*x+b" if they don't share the same 'x'. And take same "x" a special case


  • 0

    Java, O(n^2) solution, calc the "a" & "b" in "y=a*x+b" if they don't share the same 'x', and use the pair (a, b) as the key of HashMap, using a list of index (not the Point itself, I wasted some time on this) as the value.
    Points of the same "x" is a little special. In this case, use "x" as the key, same type of 'value' as last case.

    /**
     * Definition for a point.
     * class Point {
     *     int x;
     *     int y;
     *     Point() { x = 0; y = 0; }
     *     Point(int a, int b) { x = a; y = b; }
     * }
     */
    public class Solution {
        
        private static class Line{
            private static final double DELTA = 0.00001;
            public double a;
            public double b;
            
            @Override
            public boolean equals(Object o) {
                return o instanceof Line
                        && Math.abs(((Line)o).a - a) <= DELTA
                        && Math.abs(((Line)o).b - b) <= DELTA;
            }
            @Override
            public int hashCode() {
                return (int) (65536 * a + b);
            }
        }
        
        public int maxPoints(Point[] points) {
            if(points == null) {
                return 0;
            }
            if(points.length <=1) {
                return points.length;
            }
            HashMap<Integer, ArrayList<Integer>> sameXMap = new HashMap<Integer, ArrayList<Integer>>();
            HashMap<Line, ArrayList<Integer>> lineMap = new HashMap<Line, ArrayList<Integer>>();
            int max = 0;
            for(int i = 0; i < points.length - 1 ;i++){
                for (int j = i + 1; j < points.length; j++) {
                    ArrayList<Integer> list = new ArrayList<Integer>();
                    if(points[i].x == points[j].x) {
                        if(!sameXMap.containsKey(points[i].x)){
                            sameXMap.put(points[i].x, list);
                        } else {
                            list = sameXMap.get(points[i].x);
                        }
                    } else {
                        Line line = new Line();
                        line.a = (double) (points[i].y - points[j].y) / (double)(points[i].x - points[j].x);
                        line.b = points[i].y - line.a * points[i].x;
                        if(!lineMap.containsKey(line)) {
                            lineMap.put(line, list);
                        } else {
                            list = lineMap.get(line);
                        }
                    }
                    if(!list.contains(i)){
                        list.add(i);
                    }
                    if(!list.contains(j)){
                        list.add(j);
                    }
                    max = Math.max( max, list.size());
                }
            }
            return max;
        }
    }
    

Log in to reply
 

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