149.Max Points on a Line

Tag: [Math], [Map], [Double], [gcd]

Com: {t}

Hard: [###]

Link: https://leetcode.com/problems/max-points-on-a-line/\#/description

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

Solution: Map, GCD

/**
 * 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 == null || points.length == 0) {
            return 0;
        }

        List<Point> pointList = new ArrayList<>(Arrays.asList(points));
        Collections.sort(pointList, new Comparator<Point>() {
            @Override
            public int compare(Point p1, Point p2) {
                return p1.x - p2.x;
            }
        });

        int max = 0;
        int size = pointList.size();
        for (int i = 0; i < size; i ++) {
            Point p1 = pointList.get(i);
            Map<String, Integer> counting = new HashMap<>();
            int numOfSamePoints = 0;
            int numOfPointsOnVerticalLine = 0;
            int numOfPointsOnHorizontalLine = 0;

            for (int j = i + 1; j < size; j ++) {
                Point p2 = pointList.get(j);

                if (p1.x == p2.x && p1.y == p2.y) {
                    numOfSamePoints ++;
                } else if (p1.x == p2.x) {
                    numOfPointsOnVerticalLine ++;
                } else if (p1.y == p2.y) {
                    numOfPointsOnHorizontalLine ++;
                } else {
                    int y = p2.y - p1.y;
                    int x = p2.x - p1.x;

                    int gcd = getGCD(x, y);
                    y /= gcd;
                    x /= gcd;

                    String key = String.format("%d:%d", y, x);

                    if (counting.containsKey(key)) {
                        counting.put(key, counting.get(key) + 1);
                    } else {
                        counting.put(key, 1);
                    }
                }
            }

            int currMax = 0;
            for (Map.Entry<String, Integer> en : counting.entrySet()) {
                currMax = Math.max(currMax, en.getValue());
            }

            currMax = Math.max(currMax, numOfPointsOnVerticalLine);
            currMax = Math.max(currMax, numOfPointsOnHorizontalLine);
            currMax += numOfSamePoints + 1; // add the same points and the p1 itself.

            max = Math.max(max, currMax);
        }

        return max;
    }

    private int getGCD(int a, int b) {
        a = Math.abs(a);
        b = Math.abs(b);
        if (b == 0) {
            return a;
        }

        return getGCD(b, a % b);
    }
}

Revelation:

• 不做出发避免两数相除后产生无限不限不循环小数，因为由于Double可以表示精度的限制，两个无限不循环小数本来应该不相等，但Double可以表示的精度有限，Java或其他语言就可能认为他们相等了，要解决无限不循环小数就要避免除法，那么我们其实可以不用slope作为map的key，我们可以就用y的差和x的差来作为key，但有这种case存在，例如一组y的差和x的差为(1, 2), 另一组y的差和x的差为(2, 4), 但我们知道 1/2 == 2/4, 所以我们要对y的差和x的差计算gcd(最大公约数), 他们都除以最大公约数后再记入map.
• sort points based on x 的好处是对于每个p1 只要看他右侧的点，不用计算左侧点和p1的slope (也就是内层循环不用每次都从index= 0 开始了). 因为p1左侧的点和p1之间的slope都已经计算过了.

Note:

• Time complexity = O(n^2), n is the number of points, here we didn't calculate the time cost for calculating the gcd, the time complexity of calculating gcd = O(lgb), the explanation is here: https://zhaonanli.gitbooks.io/algorithm/content/gcd-greatest-common-divisor.html

Failed Solution:

/**
 * 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 == null || points.length == 0) {
            return 0;
        }

        List<Point> pointList = new ArrayList<>(Arrays.asList(points));
        Collections.sort(pointList, new Comparator<Point>() {
            @Override
            public int compare(Point p1, Point p2) {
                return p1.x - p2.x;
            }
        });

        int max = 0;
        int size = pointList.size();
        for (int i = 0; i < size; i ++) {
            Point p1 = pointList.get(i);
            Map<Double, Integer> counting = new HashMap<>();
            int numOfSamePoints = 0;
            int numOfPointsOnVerticalLine = 0;
            int numOfPointsOnHorizontalLine = 0;

            for (int j = i + 1; j < size; j ++) {
                Point p2 = pointList.get(j);

                if (p1.x == p2.x && p1.y == p2.y) {
                    numOfSamePoints ++;
                } else if (p1.x == p2.x) {
                    numOfPointsOnVerticalLine ++;
                } else if (p1.y == p2.y) {
                    numOfPointsOnHorizontalLine ++;
                } else {
                    double slope = (double)(p2.y - p1.y) / (double)(p2.x - p1.x);
                    long roundSlope = Math.round(slope * 1000000000000000000L);

                    if (counting.containsKey(slope)) {
                        counting.put(slope, counting.get(slope) + 1);
                    } else {
                        counting.put(slope, 1);
                    }
                }
            }

            int currMax = 0;
            for (Map.Entry<Double, Integer> en : counting.entrySet()) {
                currMax = Math.max(currMax, en.getValue());
            }

            currMax = Math.max(currMax, numOfPointsOnVerticalLine);
            currMax = Math.max(currMax, numOfPointsOnHorizontalLine);
            currMax += numOfSamePoints + 1; // add the same points and the p1 itself.

            max = Math.max(max, currMax);
        }

        return max;
    }
}

Revelation:

• Cannot pass the case: points = [[0, 0], [94911151, 94911150], [94911152, 94911151]], 因为Double的精度有限无法完整的表示无限不循环小数.