0149：直线上最多的点数（★★）

2015-05-29 约 272 字预计阅读 1 分钟次阅读

力扣第 149 题

题目

给你一个数组 points ，其中 points[i] = [x_i, y_i] 表示 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
-10⁴ <= x_i, y_i <= 10⁴
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

目录

0149：直线上最多的点数（★★）

题目

分析

解答