149. Max Points on a Line

09/16/2021

Leetcode

Basic Idea

一个点和一个斜率可以确定一条直线。基本思路就是从每个点出发，包含这个点，考虑其他所有的点与之相连线的斜率，按照斜率统计频率，因为都包含这个点，所以斜率的频数就是直线上点的个数。返回最大值。

需要注意当斜率为0或者为无穷时候的特殊处理。

Java Code

class Solution {
    public int maxPoints(int[][] points) {
        if (points.length == 1) {
            return 1;
        }
        int ret = 0;
        for (int i = 0; i < points.length; ++i) {
            int[] p1 = points[i];
            Map<Double, Integer> map = new HashMap<>();
            // 只需要考虑后面出现的点，因为前面的点之前已经考虑过
            for (int j = i + 1; j < points.length; ++j) {
                int[] p2 = points[j];
                int dx = p2[0] - p1[0];
                int dy = p2[1] - p1[1];
                double ratio = 0;
                if (dx == 0) {
                    ratio = Double.MIN_VALUE;
                } else if (dy == 0) {
                    ratio = 0;
                } else {
                    ratio = (double) dy / dx;
                }
                map.put(ratio, map.getOrDefault(ratio, 1) + 1);
                ret = Math.max(ret, map.get(ratio));
            }
        }
        return ret;
    }
}