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.

Solution1 (NOT GOOD)：hashmap存斜率

对于每一个点a，遍历其他点b求出各点b到它的斜率，通过hashmap来保存(k, count)来统计出含有a点的线上(不同k)最多点的个数。
存在问题：极端int x, y 浮点型的斜率k的精度会存在问题
Time Complexity: O(n^2) Space Complexity: O(n)

Solution2：hashmap 对不同点a 斜率分量： map((delta(x), delta(y)) -> count)

对于每一个点a，Compared to 直接存斜率，这里采用存斜率分量delta的方法：遍历其他点b求出各点b到a的斜率分量 delta(x), delta(y)，delta(x)= points[j].x - a.x, y同理; 保存map((delta(x), delta(y)) -> count)，(delta(x), delta(y))是经过约分最简化后的，对于a点，一对儿delta(x), delta(y)与一条直线一一对应，(等同斜率的作用，但没有精度问题）。
如此，对于所有点a, 在map((delta(x), delta(y)) -> count) 上来统计出含有a点的不同线上( 不同pair(delta(x), delta(y)) ) 最多点的个数。

          b
        /|
       / | 
      /  | delta(y)
     /   |
    a-----
     delta(x)

Time Complexity: O(n^2) Space Complexity: O(n)

Solution2 Code：

class Solution {
    public int maxPoints(Point[] points) {
            if (points == null) return 0;
            if (points.length <= 2) return points.length;
            
            Map<Integer, Map<Integer, Integer>> map = new HashMap<Integer, Map<Integer, Integer>>();
            int result = 0;

            for (int i = 0; i < points.length; i++) { 
                map.clear();
                int overlap = 0, max = 0;
                for (int j = i + 1; j < points.length; j++) {
                    int x = points[j].x - points[i].x;
                    int y = points[j].y - points[i].y;

                    if (x == 0 && y == 0){
                        overlap++;
                        continue;
                    }

                    // reduction        
                    int gcd = generateGCD(x, y);
                    if (gcd != 0){
                        x /= gcd;
                        y /= gcd;
                    }
                    
                    // count
                    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);
                    }

                    // update max
                    max = Math.max(max, map.get(x).get(y));
                }
                result = Math.max(result, max + overlap + 1);
            }
            return result;
        }
        
        private int generateGCD(int a, int b) {
            if (b == 0) return a;
            else return generateGCD(b, a % b);
        }
}