原文链接: https://leetcode-cn.com/problems/max-points-on-a-line

英文原文

Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane, return the maximum number of points that lie on the same straight line.

 

Example 1:

Input: points = [[1,1],[2,2],[3,3]]
Output: 3

Example 2:

Input: points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4

 

Constraints:

• 1 <= points.length <= 300
• points[i].length == 2
• -104 <= xi, yi <= 104
• All the points are unique.

中文题目

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

 

示例 1：

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

示例 2：

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

 

提示：

• 1 <= points.length <= 300
• points[i].length == 2
• -104 <= xi, yi <= 104
• points 中的所有点 互不相同

通过代码

高赞题解

朴素解法（枚举直线 + 枚举统计）

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

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

为了避免除法精度问题，当我们枚举两个点 $i$ 和 $j$ 时，不直接计算其对应直线的 斜率和 截距，而是通过判断 $i$ 和 $j$ 与第三个点 $k$ 形成的两条直线斜率是否相等（斜率相等的两条直线要么平行，要么重合，平行需要 $4$ 个点来唯一确定，我们只有 $3$ 个点，所以可以直接判定两直线重合）。

代码：

[]
class Solution {
    public int maxPoints(int[][] ps) {
        int n = ps.length;
        int ans = 1;
        for (int i = 0; i < n; i++) {
            int[] x = ps[i];
            for (int j = i + 1; j < n; j++) {
                int[] y = ps[j];
                int cnt = 2;
                for (int k = j + 1; k < n; k++) {
                    int[] p = ps[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;
    }
}

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

---

优化（枚举直线 + 哈希表统计）

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

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

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

代码：

[]
class Solution {
    public int maxPoints(int[][] ps) {
        int n = ps.length;
        int 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 = ps[i][0], y1 = ps[i][1], x2 = ps[j][0], y2 = ps[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);
    }
}

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

统计信息

通过次数	提交次数	AC比率
49921	143538	34.8%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
直线镜像	中等