题目
暴力解法:O(n^3)
class Solution:def maxPoints(self, points: List[List[int]]) -> int:n = len(points)if n<=1:return nmax_count = 0for i in range(n):x1,y1 = points[i]for j in range(i+1,n):x2,y2 = points[j]line1 = (y2-y1)/(x2-x1) if x2-x1 else float('inf')count = 0pair = (points[i],points[j])for k in range(n):x3,y3 = points[k]line2 = (y3-y2)/(x3-x2) if x3-x2 else float('inf')if line1 == line2 or points[k] in pair:count += 1max_count = max(max_count,count)return max_count
利用hashmap优化
先把所有可能的斜率算出来，然后再过一遍points即可
这边要注意浮点数的精确计算。上面的解法由于是直接比较斜率，没有牵涉到储存，但是这边有一步斜率的储存，所以直接浮点数储存是不太对的。比如[[0,0],[94911151,94911150],[94911152,94911151]]，这个例子用浮点数算的话，1，2两点和1，3两点因为精度的问题算出来会是一样的。所以这边计算斜率的时候用decimal就阔以了。有另外一种思路，不用decimal，而直接用分数表示斜率。只需要判断两个分数斜率的交叉成绩是否相等就可以了，也不用进行约分。比如a/b和c/d，只需判断ad==bc就可以
class Solution:def maxPoints(self, points: List[List[int]]) -> int:from decimal import Decimaln = len(points)if n<=1:return nslope2pair = {
}for i in range(n):x1,y1 = points[i]for j in range(i+1,n):x2,y2 = points[j]slope = Decimal(y2-y1)/Decimal(x2-x1) if x2-x1 else float('inf')count = 0pair = (points[i],points[j])slope2pair[slope] = pairmax_count = 0for slope,pair in slope2pair.items():x1,y1 = pair[0]count = 0for point in points:x3,y3 = pointslope_now = Decimal(y3-y1)/Decimal(x3-x1) if x3-x1 else float('inf')if point in pair or slope_now == slope:count += 1max_count = max(max_count,count)return max_count