Java Accepted Solution o(n^2)


  • 0

    The idea is to use slope and intercept to specify a line. Instead of using double, which could have precision problem, I use int array to specify params for a line. GCD is used to make numerator and denominator to be co-prime. Two corner cases need to be considered: vertical and horizontal line.

    /**
     * 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 {
        public int maxPoints(Point[] points) {
            if (points.length == 1) return 1;
            HashMap<Line, HashSet<Integer>> hash = new HashMap<Line, HashSet<Integer>>();
            for (int i = 0; i < points.length; i++) {
                for (int j = i+1; j < points.length; j++) {
                    Line slope = computeSlope(points[i], points[j]);
                    if (!hash.containsKey(slope)) hash.put(slope, new HashSet<Integer>());
                    // System.out.println(slope);
                    hash.get(slope).addAll(Arrays.asList(i,j));
                }
            }
            int max = 0;
            for (HashSet<Integer> set: hash.values()) {
                max = Math.max(max, set.size());
            }
            return max;
        }
        // y-y1 = k*(x-x1)
        // y = (y2-y1)/(x2-x1)*x +(y1*(x2-x1)- x1*(y2-y1))/(x2-x1)
        private Line computeSlope(Point a, Point b) {
            int[] result = new int[4];
            
            if (b.x-a.x == 0) {
                result[0] = Integer.MAX_VALUE;
                result[1] = 0;
                result[2] = a.x;
                result[3] = 0;
            } else if (b.y-a.y == 0) {
                result[0] = 0;
                result[1] = 0;
                result[2] = 0;
                result[3] = a.y;
            } else {
                int n = b.y-a.y;
                int d = b.x-a.x;
                int g = gcd(Math.abs(n), Math.abs(d));
                if ((n > 0 && d > 0)||(n < 0 && d < 0)) {
                    result[0] = Math.abs(n)/g;
                    result[1] = Math.abs(d)/g;
                } else {
                    result[0] = -Math.abs(n)/g;
                    result[1] = Math.abs(d)/g;
                }
                
                n = a.y*(b.x-a.x)-a.x*(b.y-a.y);
                d = b.x-a.x;
                g = gcd(Math.abs(n), Math.abs(d));
                if ((n > 0 && d > 0)||(n < 0 && d < 0)) {
                    result[2] = Math.abs(n)/g;
                    result[3] = Math.abs(d)/g;
                } else {
                    result[2] = -Math.abs(n)/g;
                    result[3] = Math.abs(d)/g;
                }
            }
            
            return new Line(result);
        }
        
        class Line{
            public int[] params = null;
            public Line(int[] params) {
                this.params = params;
            }
            
            public int hashCode() {
                long res = 0;
                for (int n: params) {
                    res = res*37+n;
                }
                return (int)res;
            }
            
            public boolean equals(Object a){
                if (a == null) return false;
                for (int i = 0; i < this.params.length; i++) {
                    if (this.params[i] != ((Line)a).params[i]) return false;
                }
                return true;
            }
        }
        
        private int gcd (int a, int b) {
            if (b == 0) return a;
            return gcd(b, a%b);
        }
    }

Log in to reply
 

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