Leetcode 149. 直线上最多的点数

发表于
| 字数统计: 869 | 阅读时长 ≈ 3

题目描述

给定一个二维平面，平面上有 n 个点，求最多有多少个点在同一条直线上。

示例 1:

1
2
3
4
5
6
7
8
9
10
输入: [[1,1],[2,2],[3,3]]
输出: 3
解释:
^
|
|        o
|     o
|  o  
+------------->
0  1  2  3  4

示例 2:

1
2
3
4
5
6
7
8
9
10
11
输入: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
输出: 4
解释:
^
|
|  o
|     o        o
|        o
|  o        o
+------------------->
0  1  2  3  4  5  6

分析

如何判断一个点在某条直线上？

我们知道一条直线可以用$y=kx+b$来表示，如果点$(x,y)$满足上式则表明$(x,y)$在直线$y=kx+b$上。

这样的话，对于points中的每个点，可以分别计算其和其它每个点形成的直线，而这些直线重复数量的最大值就是经过该点的直线所能经过的最大点数。

举个例子：

points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]，对于$a=(1, 1)$来说，它和$b=(3, 2)$形成的直线为
$$y = \frac{1}{2}x+\frac{1}{2}$$其中
$$k=\frac{a[0]-b[0]}{a[1]-b[1]}$$
$$b = b[1]-k*b[0]$$

同理，$a=(1, 1)$和剩余的点形成的直线分别为$y = \frac{1}{2}x+\frac{1}{2}$，$y = 1$，$y = 2x-1$和$x = 1$。

观察上述直线的$k$，可以发现其中有两个值为$1/2$，一个值为$2$，还有$inf$和$0$各一个。
我们可以用$k$作为键值的hashmap来记录这些数据出现的次数，这样就能在$O(1)$的时间内完成更新的操作，因为需要更新N个点，所以总体时间复杂度为$O(N)$。

最后在hashmap中取最大的值加一就是就是经过该点的直线所能经过的最大点数。

对于数组中的每个点进行上述操作取结果最大值就是题目所要求的数，最终时间复杂度为$O(N^2)$。

注意：

  1. 测试用例中存在重复点的情况，比如[[0,0],[0,0]]，代码中需要判断两点坐标是否相同，如果相同那么结果直接+1就不需要更新hashmap了。

  2. 两点可能在一条竖线上，这样就无法计算出$k$，因为$a[1]-b[1]=0$，数不能被0除，要特殊处理。

    代码

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
from collections import *
class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        # i是需要判断点的索引
        def calc(points, i):
            # defaultdict是collections里的一个类，就是带有默认值的字典
            # 这样不用在给字典赋值时先判断key存不存在了
            hashmap = defaultdict(int)
            # 记录与需要判断点重合点的数目
            same = 0
            for j in range(len(points)):
                # 不对同一个点进行计算
                if j != i:
                    # 如果两点坐标相同same加一然后跳回循环开始
                    if points[i] == points[j]:
                        same += 1
                        continue
                    # 因为可能存在斜率无穷大的情况，提前做判断
                    if points[i][1] - points[j][1] == 0:
                        k = float('Inf')
                    else:
                        k = (points[i][0] - points[j][0]) / (points[i][1] - points[j][1])
                    # 最后更新hashmap
                    hashmap[k] += 1
            # 取hashmap中最大值加上重复的个数再加一就是该点的结果
            return 1 + same + (max(hashmap.values()) if hashmap else 0)
        res = 0
        if len(points) == 1: return 1
        # 对于每个点进行一次calc操作，取最大值作为答案
        for i in range(len(points)):
            res = max(res, calc(points, i))
        return res

—s
执行用时 :104 ms, 在所有 Python3 提交中击败了66.67%的用户
内存消耗 :13 MB, 在所有 Python3 提交中击败了100.00%的用户