Posted on 2023-01-08 18:10
Uriel 閱讀(58)
評論(0) 編輯 收藏 引用 所屬分類:
計算幾何 、
閑來無事重切Leet Code
給出一堆二維點，問最多多少個點共線
O(n
2)枚舉兩個點，看一樣斜率的最多多少個點，2014年曾經用C++寫過??http://www.shnenglu.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