面试题 16.14. 最佳直线

题目

给定一个二维平面及平面上的 N 个点列表Points，其中第i个点的坐标为Points[i]=[Xi,Yi]。请找出一条直线，其通过的点的数目最多。

设穿过最多点的直线所穿过的全部点编号从小到大排序的列表为S，你仅需返回[S[0],S[1]]作为答案，若有多条直线穿过了相同数量的点，则选择S[0]值较小的直线返回，S[0]相同则选择S[1]值较小的直线返回。

示例：
输入： [[0,0],[1,1],[1,0],[2,0]]
输出： [0,2]
解释：所求直线穿过的3个点的编号为[0,2,3]

提示：

2 <= len(Points) <= 300
len(Points[i]) = 2

题解

public int[] bestLine(int[][] points) {
    // 第1、2位为索引 第3位为经过点的数量
    Map<String, int[]> lines = new HashMap<>(8);
    // 最大公约数
    BiFunction<Integer, Integer, Integer> gcd = new BiFunction<Integer, Integer, Integer>() {
        @Override
        public Integer apply(Integer a, Integer b) {
            return b == 0 ? a : this.apply(b, a % b);
        }
    };
    // 直线公式 A*x + B*y + C = 0 返回 A、B、C list
    BiFunction<int[], int[], String> line = (p1, p2) -> {
        int x1 = p1[0], y1 = p1[1], x2 = p2[0], y2 = p2[1];
        int x0 = x2 - x1, y0 = y2 - y1;
        int a = y0, b = -x0, c = x0 * y1 - y0 * x1;
        // 若A、B、C存在公约数
        int g = gcd.apply(gcd.apply(a, b), c);
        a /= g;
        b /= g;
        c /= g;
        // 生成方程式的key
        return String.format("%d_%d_%d", a, b, c);
    };
    // 缓存最大
    AtomicReference<int[]> max = new AtomicReference<>(new int[]{0, 1, 2});
    for (int i = 1; i < points.length; i++) {
        // 从小到大 保证第一次出现的为小索引到大索引
        for (int j = 0; j < i; j++) {
            lines.merge(line.apply(points[i], points[j]), new int[]{j, i, 2}, (o, n) -> {
                // 若已存在一条直线 则累加点数量
                o[2]++;
                // 存数量最多 索引位置较小的
                if (o[2] > max.get()[2] || (o[2] == max.get()[2] && o[0] < max.get()[0])) {
                    max.set(o);
                }
                return o;
            });
        }
    }

    return Arrays.copyOfRange(max.get(), 0, 2);
}