LC 149. 直线上最多的点数

题目描述

这是 LeetCode 上的 149. 直线上最多的点数 ，难度为困难。

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

示例 1：

1
2
3

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

输出：3

示例 2：

1
2
3

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

输出：4

提示：

$1 <= points.length <= 300$
$points[i].length == 2$
$-10^4 <= x_i, y_i <= 10^4$
points 中的所有点互不相同

枚举直线 + 枚举统计

我们知道，两点可以确定一条线。

一个朴素的做法是先枚举两点（确定一条线），然后检查其余点是否落在该线中。

为避免除法精度问题，当我们枚举两个点 $x$ 和 $y$ 时，不直接计算其对应直线的 斜率和 截距。

而是通过判断 $x$ 和 $y$ 与第三个点 $p$ 形成的两条直线斜率是否相等，来得知点 $p$ 是否落在该直线上。

斜率相等的两条直线要么平行，要么重合。

平行需要 $4$ 个点来唯一确定，我们只有 $3$ 个点，因此直接判定两条直线是否重合即可。

详细说，当给定两个点 $(x_1, y_1)$ 和 $(x_2, y_2)$ 时，对应斜率 $\frac{y_2 - y_1}{x_2 - x_1}$。

为避免计算机除法的精度问题，我们将「判定 $\frac{a_y - b_y}{a_x - b_x} = \frac{b_y - c_y}{b_x - c_x}$ 是否成立」改为「判定 $(a_y - b_y) \times (b_x - c_x) = (a_x - b_x) \times (b_y - c_y)$ 是否成立」。

将存在精度问题的「除法判定」巧妙转为「乘法判定」。

Java 代码：

class Solution {
    public int maxPoints(int[][] points) {
        int n = points.length, ans = 1;
        for (int i = 0; i < n; i++) {
            int[] x = points[i];
            for (int j = i + 1; j < n; j++) {
                int[] y = points[j];
                // 枚举点对 (i,j) 并统计有多少点在该线上, 起始 cnt = 2 代表只有 i 和 j 两个点在此线上
                int cnt = 2;
                for (int k = j + 1; k < n; k++) {
                    int[] p = points[k];
                    int s1 = (y[1] - x[1]) * (p[0] - y[0]);
                    int s2 = (p[1] - y[1]) * (y[0] - x[0]);
                    if (s1 == s2) cnt++;
                }
                ans = Math.max(ans, cnt);
            }
        }
        return ans;
    }
}

C++ 代码：

class Solution {
public:
    int maxPoints(vector<vector<int>>& points) {
        int n = points.size(), ans = 1;
        for (int i = 0; i < n; i++) {
            vector<int> x = points[i];
            for (int j = i + 1; j < n; j++) {
                vector<int> y = points[j];
                // 枚举点对 (i,j) 并统计有多少点在该线上, 起始 cnt = 2 代表只有 i 和 j 两个点在此线上
                int cnt = 2;
                for (int k = j + 1; k < n; k++) {
                    vector<int> p = points[k];
                    int s1 = (y[1] - x[1]) * (p[0] - y[0]);
                    int s2 = (p[1] - y[1]) * (y[0] - x[0]);
                    if (s1 == s2) cnt++;
                }
                ans = max(ans, cnt);
            }
        }
        return ans;
    }
};

Python 代码：

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        n, ans = len(points), 1
        for i, x in enumerate(points):
            for j in range(i + 1, n):
                y = points[j]
                # 枚举点对 (i,j) 并统计有多少点在该线上, 起始 cnt = 2 代表只有 i 和 j 两个点在此线上
                cnt = 2
                for k in range(j + 1, n):
                    p = points[k]
                    s1 = (y[1] - x[1]) * (p[0] - y[0])
                    s2 = (p[1] - y[1]) * (y[0] - x[0])
                    if s1 == s2: cnt += 1
                ans = max(ans, cnt)
        return ans

TypeScript 代码：

function maxPoints(points: number[][]): number {
    let n = points.length, ans = 1;
    for (let i = 0; i < n; i++) {
        let x = points[i];
        for (let j = i + 1; j < n; j++) {
            // 枚举点对 (i,j) 并统计有多少点在该线上, 起始 cnt = 2 代表只有 i 和 j 两个点在此线上
            let y = points[j], cnt = 2;
            for (let k = j + 1; k < n; k++) {
                let p = points[k];
                let s1 = (y[1] - x[1]) * (p[0] - y[0]);
                let s2 = (p[1] - y[1]) * (y[0] - x[0]);
                if (s1 == s2) cnt++;
            }
            ans = Math.max(ans, cnt);
        }
    }
    return ans;
};

时间复杂度：$O(n^3)$
空间复杂度：$O(1)$

枚举直线 + 哈希表统计

根据「朴素解法」的思路，枚举所有直线的过程不可避免，但统计点数的过程可以优化。

具体的，我们可以先枚举所有可能出现的 直线斜率（根据两点确定一条直线，即枚举所有的「点对」），使用「哈希表」统计所有 斜率 对应的点的数量，在所有值中取个 $max$ 即是答案。

一些细节：在使用「哈希表」进行保存时，为了避免精度问题，我们直接使用字符串进行保存，同时需要将 斜率 约干净。

Java 代码：

class Solution {
    public int maxPoints(int[][] points) {
        int n = points.length, ans = 1;
        for (int i = 0; i < n; i++) {
            Map<String, Integer> map = new HashMap<>();
            // 由当前点 i 发出的直线所经过的最多点数量
            int max = 0;
            for (int j = i + 1; j < n; j++) {
                int x1 = points[i][0], y1 = points[i][1], x2 = points[j][0], y2 = points[j][1];
                int a = x1 - x2, b = y1 - y2;
                int k = gcd(a, b);
                String key = (a / k) + "_" + (b / k);
                map.put(key, map.getOrDefault(key, 0) + 1);
                max = Math.max(max, map.get(key));
            }
            ans = Math.max(ans, max + 1);
        }
        return ans;
    }
    int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

C++ 代码：

class Solution {
public:
    int maxPoints(vector<vector<int>>& points) {
        int n = points.size(), ans = 1;
        for (int i = 0; i < n; i++) {
            map<string, int> map;
            int maxv = 0;
            for (int j = i + 1; j < n; j++) {
                int x1 = points[i][0], y1 = points[i][1], x2 = points[j][0], y2 = points[j][1];
                int a = x1 - x2, b = y1 - y2;
                int k = gcd(a, b);
                string key = to_string(a / k) + "_" + to_string(b / k);
                map[key]++;
                maxv = max(maxv, map[key]);
            }
            ans = max(ans, maxv + 1);
        }
        return ans;
    }
    int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
};

Python 代码：

class Solution:
    def maxPoints(self, points):
        def gcd(a, b):
            return a if b == 0 else gcd(b, a % b)
        
        n, ans = len(points), 1
        for i in range(n):
            mapping = {}
            maxv = 0
            for j in range(i + 1, n):
                x1, y1 = points[i]
                x2, y2 = points[j]
                a, b = x1 - x2, y1 - y2
                k = gcd(a, b)
                key = str(a // k) + "_" + str(b // k)
                mapping[key] = mapping.get(key, 0) + 1
                maxv = max(maxv, mapping[key])
            ans = max(ans, maxv + 1)    
        return ans

TypeScript 代码：

function maxPoints(points: number[][]): number {
    const gcd = function(a: number, b: number): number {
        return b == 0 ? a : gcd(b, a % b);
    }
    let n = points.length, ans = 1;
    for (let i = 0; i < n; i++) {
        let mapping = {}, maxv = 0;
        for (let j = i + 1; j < n; j++) {
            let x1 = points[i][0], y1 = points[i][1], x2 = points[j][0], y2 = points[j][1];
            let a = x1 - x2, b = y1 - y2;
            let k = gcd(a, b);
            let key = `${a / k}_${b / k}`;
            mapping[key] = mapping[key] ? mapping[key] + 1 : 1;
            maxv = Math.max(maxv, mapping[key]);
        }
        ans = Math.max(ans, maxv + 1);
    }
    return ans;
};

时间复杂度：枚举所有直线的复杂度为 $O(n^2)$；令坐标值的最大差值为 $m$，gcd 复杂度为 $O(\log{m})$。整体复杂度为 $O(n^2 \times \log{m})$
空间复杂度：$O(n)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.149 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

哈希表数学枚举

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

LC 752. 打开转盘锁上一篇

LC 剑指 Offer 15. 二进制中1的个数下一篇