直线上最多的点数

给你一个数组 points ，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。

  • 输入：points = [[1,1],[2,2],[3,3]]

  • 输出：3

  • 输入：points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]

  • 输出：4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
var maxPoints = function(points) {
    let ans = 1;
    const n = points.length, map = new Map();
    for (let i = 0; i < n; i++) {
        if (ans >= n - i) break;
        const x1 = points[i][0], y1 = points[i][1];
        for (let j = i + 1; j < n; j++) {
            const x2 = points[j][0], y2 = points[j][1];
            let k = 0, b = 0;
            if (y1 === y2) {
                k = Infinity;
                b = y1;
            } else if (x1 === x2) {
                k = 0;
                b = x1;
            } else {
                k = (x1 - x2) / (y1 - y2);
                b = (x2 * y1 - y2 * x1) / (x2 - x1);
            }
            const sum = (map.get(`${k}:${b}`) || 1) + 1
            map.set(`${k}:${b}`, sum);
            if (sum > ans) ans = sum;
        }
        map.clear();
    }
    return ans;
};