Posted on 2023-01-08 18:10
Uriel 阅读(38)
评论(0) 编辑 收藏 引用 所属分类:
计算几何 、
闲来无事重切Leet Code
给出一堆二维点，问最多多少个点共线
O(n
2)枚举两个点，看一样斜率的最多多少个点，2014年曾经用C++写过👉http://www.cppblog.com/Uriel/articles/205287.html
今日在Discussion看到个不错的思路（👉https://leetcode.com/problems/max-points-on-a-line/solutions/3016632/python-3-11-lines-w-explanation-and-example-t-m-95-97/），不需要折腾double型求斜率，因为点的坐标都是int型，可以求两个点dx，dy，除以GCD之后用dict统计这样的约简后的数对有多少个，因为存的是除以GCD之后的数对，所以一开始要给所有点按x值从小到大排序，保证单调增
1 #149
2 #Runtime: 77 ms (Beats 92.29%)
3 #Memory: 13.8 MB (Beats 94.26%)
4
5 class Solution:
6 def maxPoints(self, points: List[List[int]]) -> int:
7 points.sort()
8 ans = 0
9 for i, (x1, y1) in enumerate(points):
10 k = defaultdict(int)
11 for x2, y2 in points[i + 1 :]:
12 dx = x2 - x1
13 dy = y2 - y1
14 g = gcd(dx, dy)
15 kk = (dx // g, dy // g)
16 k[kk] += 1
17 ans = max(ans, k[kk])
18 return ans + 1