149. 直线上最多的点数
149. 直线上最多的点数
class MaxPoints:"""149. 直线上最多的点数https://leetcode.cn/problems/max-points-on-a-line/description/?envType=study-plan-v2&envId=top-interview-150"""def solution(self, points: List[List[int]]) -> int:"""时间复杂度 O(n^2 * log n)空间复杂度 O(log n):param points: :return: """n = len(points)if n <= 2:return nans = 0for i in range(n):if ans >= n - i or ans > n // 2:breakhm = dict()for j in range(i + 1, n):x = points[i][0] - points[j][0]y = points[i][1] - points[j][1]if x == 0:y = 1elif y == 0:x = 1else:if y < 0:x = -xy = -ygcd_xy = self.gcd(abs(x), abs(y))x /= gcd_xyy /= gcd_xy# 将x缩放20001倍，可以理解为原本相邻x1，x2的距离由 1 放大至 20001，这样 无论y取任何[0, 2×10^4]中的值，# 都可以映射到这个间隔内，保证了任意两组数（x1，y1）和 （x2，y2），只要有一个值（x1 != x2 或 y1 != y2）不同，# 那映射后的val1 和 val2 也不同val = y + x * 20001hm[val] = hm.get(val, 0) + 1max_n = 0for k, v in hm.items():max_n = max(max_n, v + 1)ans = max(ans, max_n)return ansdef gcd(self, a, b):"""求a和b的最大公约数，时间复杂度 log n:param a::param b::return:"""if b == 0:return areturn self.gcd(b, a % b)