LeetCode 149. 直线上最多的点数
LeetCode 149. 直线上最多的点数
给你一个数组 points ,其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。
示例 1:
输入:points = [[1,1],[2,2],[3,3]]
输出:3
示例 2:
输入:points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
输出:4
提示:
1 <= points.length <= 300
points[i].length == 2
-104 <= xi, yi <= 104
points 中的所有点 互不相同
恰巧AC,但题解不对,还是看大佬的解法吧
class Solution:def maxPoints(self, points: List[List[int]]) -> int:if len(points) == 1:return 1combine_mapping = {}for i in range(2, len(points) + 1):combine_mapping[math.comb(i, 2)] = imapping = defaultdict(lambda: 0)mapping[(0,0,0)] = 1for i in range(len(points)):for j in range(i + 1, len(points)):(x1, y1), (x2, y2) = points[i], points[j]a, b, c = y2 - y1, x1 - x2, x2 * y1 - x1 * y2d = a if a else ba, b, c = a / d, b / d, c / dmapping[(a, b, c)] += 1res = (0,0,0)for i in mapping:if combine_mapping[mapping[res]] <= combine_mapping[mapping[i]]:res = ireturn combine_mapping[mapping[res]]