目录

0149:直线上最多的点数(★★)

力扣第 149 题

题目

给你一个数组 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 中的所有点 互不相同

相似问题:

分析

  • 本题可能有重复点,因此考虑按点遍历更方便:
    • 对于每个点,首先统计重复个数 same
    • 然后将其它点按斜率分组
    • 最大的组大小加上 same 即可
  • 考虑到精度问题,可以用最简分数来表示斜率,注意不存在斜率的特殊情况

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        def cal(x,y):
            if y==0:
                return (1,0)
            if y<0:
                return cal(-x,-y)
            a = gcd(x,y)
            return (x//a,y//a)
        res = 0
        for a in points:
            same = points.count(a)
            ct = Counter(cal(b[0]-a[0],b[1]-a[1]) for b in points if b!=a)
            res = max(res,max(ct.values(),default=0)+same)
        return res

212 ms