算法刷题目其他题目
Source
Edit
History

直线上最多的点数

一、题目

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

Leetcode：https://leetcode.cn/problems/max-points-on-a-line/description/

二、分析

如果点 i 和点 j 所连直线的斜率等于点 i 和点 k 所连直线的斜率。那么我们说 i、j、k 三个点在同一条直线上。

我们可以统计其他所有点与点 i 所连直线的斜率，出现次数最多的斜率即为经过点数最多的直线的斜率，其经过的点数为该斜率出现的次数加一（点 i 自身也要被统计）。

斜率如何计算，比如两个点：(x1, y1), (x2, y2)。他们的斜率为：(y1-y2)/(x1-x2)。注意对于 1/2 和 2/4 这两个斜率是相同的，因此我们需要将他们化简为最简分数的形式。最大公约数的求法可以使用辗转相除法。

1
2
3
4
5
6
7
8
x' = x1-x2
y' = y1-y2
斜率 slope = y' / x'
最大公约数 gcd(|x'|, |y'|)
将分子和分母同时除以二者绝对值的最大公约数，可得：
mx = x' / gcd(|x'|, |y'|)
my = y' / gcd(|x'|, |y'|)
因此斜率为 slope = mx / my

考虑到 mx 和 my 两数其中有一个为 0 的情况。也就是水平线和垂直线。此时不存在数学意义上的最大公约数，因此我们直接将这两种情况特殊化，当 mx 为 0 时，我们令 my=1；当 my 为 0 时，我们令 mx=1 即可。

此外，因为分子、分母可能存在负数，为了防止出现 (-1 / 2) = (1 / -2) 的情况，因此我们规定分子为非负整数，如果 my 为负数，我们将 mx 和 my 都取反。

同时，由于牵扯到除法，浮点数类型可能因为精度不够而无法足够精确地表示每一个斜率。因此我们将其转换为一个整数。

在本题中，因为点的横纵坐标取值范围均为 [-10^4, 10^4]，所以 mx 落在区间 [-2 * 10^4, 2 * 10^4] 内。是因为 10^4 - (-10^4) = -2 * 10^4。同理，因为 my 不为负数，所以 my 落在区间 [0, 2 * 10^4]。我们发现 32 位整数的范围远远超过这两个区间，因为我们用单个 32 位整形变量来表示这两个整数。如下：

1
2
3
val = my + (2 * 10^4 + 1) * mx
给 mx 乘以 (2 * 10^4 + 1)，让 mx 落在 [2 * 10^4 + 1, xxx]，不干扰 my 的区间
因为 my 区间在 [0, 2 * 10^4]

还有几个优化点：

  • 在点的总数量小于等于 2 时，我们总可以用一条直线将其所有点进行串联，此时我们直接返回总的点数即可
  • 当我们枚举到点 iii 时，我们只需要考虑编号大于 i 的点到点 i 的斜率，因为如果直线同时经过编号小于点 i 的点 j，那么当我们枚举到 j 时就已经考虑过该直线了
  • 当我们找到一条直线经过了图中超过半数的点时，我们即可以确定该直线即为经过最多点的直线
  • 当我们枚举到点 i（假设编号从 0 开始）时，我们至多只能找到 n−i 个点共线。假设此前找到的共线的点的数量的最大值为 k，如果有 k >= n-i，那么此时我们即可停止枚举，因为不可能再找到更大的答案了
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
public:
    int maxPoints(const std::vector<std::vector<int>>& points) {
        int n = points.size();
        if (n <= 2) {
            return n;
        }
        int res = 0;
        for (int i = 0; i < n; i++) {
            if (res >= n-1 || res > n/2) {
                break;
            }
            std::unordered_map<int, int> mp;
            for (int j = i+1; j < n; j++) {
                int x = points[i][0] - points[j][0];
                int y = points[i][1] - points[j][1];
                if (x == 0) {
                    y = 1;
                } else if (y == 0) {
                    x = 1;
                } else {
                    if (y < 0) {
                        x = -x;
                        y = -y;
                    }
                    int gcd_xy = gcd(std::abs(x), std::abs(y));
                    x /= gcd_xy;
                    y /= gcd_xy;
                }
                mp[y + x * 20001]++;
            }
            int max_n = 0;
            for (const auto& x : mp) {
                max_n = std::max(max_n, x.second+1);
            }
            res = std::max(res, max_n);
        }
        return res;
    }

private:
    int gcd(int a, int b) {
        return b ? gcd(b, a % b) : a;
    }
};

时间复杂度：O(n^2 * log(m))，其中 n 为点的数量，m 为横纵坐标差的最大值。最坏情况下我们需要枚举 n 个点，枚举单个点过程中需要进行 O(n) 次最大公约数计算，单次最大公约数计算的时间复杂度为 O(log(m))

空间复杂度：O(n)，其中 n 为点的数量