149. Max Points on a Line

给定一堆点，求最多有多少个点在同一直线上。

这道题被标记为Hard，而且AC率只有14.3%，刚看到是有点虚的。。。不过实际试了下之后，发现其实是道数学题。算法和数据结构上都没什么特殊的，算法只能是暴力O(N^2)，数据结构只用到Map和Set。而且时间条件很宽松，我本来很担心TLE的，结果WA了几次后居然过了。

基本思路是用一个Map记录所有出现过的直线，和直线上已经有的点。两个嵌套for循环，每两个点计算出一条直线，看这条直线是否已经出现过。没出现过则丢到Map里，已出现过则更新。

要注意的问题：

• 如何表示一条直线？我是采用y=kx+b的形式，用两个double变量（k和b）唯一表示一条直线。
• 如何处理重复的点？
• 如何处理垂直于X轴的线（斜率k为正无穷）？
• 据说double会有精度问题，比如+0.0和-0.0之类的，还有Double.NaN，不过我没遇到。可能也是leetcode的test case没覆盖到。

代码：

public class Solution {
    public int maxPoints(Point[] points) {
        // 注意边界条件
        if (points == null)
            return 0;
        if (points.length < 3)
            return points.length;

        int max = 0;
        // 为了处理重复的点，我是先去重了一次
        // WeightPoint的weight变量表示这个点出现了多少次
        // 排序是O(NlogN)，跟后面的O(N^2)相比应该不算什么吧
        List<WeightPoint> weightPoints = sortAndUniq(points);
        // 注意去重后要再判断一次边界条件
        if (weightPoints.size() <= 2) {
            for (WeightPoint p : weightPoints) {
                max += p.weight;
            }
            return max;
        }

        // 用了一个很别扭的结构来保存每条直线的信息
        // y=kx+b
        // 第一个map的key是k，第二个map的key是b，value是当前这条直线上已经有哪些点，用一个Set去重
        // 如果能用guava的Table就好了
        Map<Double, Map<Double, Set<Integer>>> map = new HashMap<Double, Map<Double, Set<Integer>>>();

        // 开始穷举，每两个点计算一次
        for (int i = 0; i < weightPoints.size(); i++) {
            for (int j = i + 1; j < weightPoints.size(); j++) {
                Point a = weightPoints.get(i), b = weightPoints.get(j);
                double x = calcSlope(a, b);   // 计算斜率k
                double y = 0;    // 计算常数b
                // 如果是垂直于x轴的直线，我会返回一个特殊值，这时b要取x坐标
                if (x == Double.MIN_VALUE) {
                    y = a.x;
                }
                // 否则就按公式计算b
                else {
                    y = a.y - x * a.x;
                }
                // 开始更新map
                if (map.containsKey(x)) {
                    if (map.get(x).containsKey(y)) {
                        Set<Integer> set = map.get(x).get(y);
                        set.add(i);
                        set.add(j);
                    } else {
                        Set<Integer> set = new HashSet<Integer>();
                        set.add(i);
                        set.add(j);
                        map.get(x).put(y, set);
                    }
                } else {
                    Set<Integer> set = new HashSet<Integer>();
                    set.add(i);
                    set.add(j);
                    Map<Double, Set<Integer>> tmp = new HashMap<Double, Set<Integer>>();
                    tmp.put(y, set);
                    map.put(x, tmp);
                }
            }
        }

        // 穷举完毕，开始计算max
        for (Double d1 : map.keySet()) {
            for (Double d2 : map.get(d1).keySet()) {
                // 计算每条直线上有多少点
                Set<Integer> set = map.get(d1).get(d2);
                int tmp = 0;
                for (Integer i : set) {
                    // 如果有重复的点，也要算进去
                    tmp += weightPoints.get(i).weight;
                }
                max = Math.max(max, tmp);
            }
        }

        return max;
    }

    // 计算斜率，注意对垂直于x轴的直线的特殊处理
    private double calcSlope(Point a, Point b) {
        if (a.x == b.x)
            return Double.MIN_VALUE;
        else
            return (double) (b.y - a.y) / (b.x - a.x);
    }

    // 判断两个点是否相同
    private boolean samePoint(Point a, Point b) {
        return a.x == b.x && a.y == b.y;
    }

    // 排序并且去重
    private List<WeightPoint> sortAndUniq(Point[] points) {
        Arrays.sort(points, new Comparator<Point>() {
            @Override
            public int compare(Point o1, Point o2) {
                int tmp = Integer.compare(o1.x, o2.x);
                if (tmp == 0)
                    return Integer.compare(o1.y, o2.y);
                else
                    return tmp;
            }
        });

        List<WeightPoint> res = new ArrayList<WeightPoint>();
        Point last = null;
        int count = 0;
        for (int i = 0; i < points.length; i++) {
            if (last == null) {
                last = points[i];
                count = 1;
                continue;
            }

            if (samePoint(last, points[i])) {
                count++;
                continue;
            }

            WeightPoint newP = new WeightPoint();
            newP.x = last.x;
            newP.y = last.y;
            newP.weight = count;
            res.add(newP);

            last = points[i];
            count = 1;
        }

        WeightPoint newP = new WeightPoint();
        newP.x = last.x;
        newP.y = last.y;
        newP.weight = count;
        res.add(newP);

        return res;
    }
}

// 一个辅助类，多了一个weight字段，用于保存每个点的出现次数
class WeightPoint extends Point {
    int weight = 1;

    public String toString() {
        return x + ":" + y + ":" + weight;
    }
}

写完之后发现，我去这个解法怎么这么长。。。虽然能AC。但纯算法题写这么多代码，一般是有问题的。应该有更好的解法，哪天有心情再折腾吧。