給出一堆二維點(diǎn)，問(wèn)最多多少個(gè)點(diǎn)共線
O(n
2)枚舉兩個(gè)點(diǎn)，看一樣斜率的最多多少個(gè)點(diǎn)，2014年曾經(jīng)用C++寫(xiě)過(guò)??http://www.shnenglu.com/Uriel/articles/205287.html
今日在Discussion看到個(gè)不錯(cuò)的思路（??https://leetcode.com/problems/max-points-on-a-line/solutions/3016632/python-3-11-lines-w-explanation-and-example-t-m-95-97/），不需要折騰double型求斜率，因?yàn)辄c(diǎn)的坐標(biāo)都是int型，可以求兩個(gè)點(diǎn)dx，dy，除以GCD之后用dict統(tǒng)計(jì)這樣的約簡(jiǎn)后的數(shù)對(duì)有多少個(gè)，因?yàn)榇娴氖浅訥CD之后的數(shù)對(duì)，所以一開(kāi)始要給所有點(diǎn)按x值從小到大排序，保證單調(diào)增
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