[Leetcode][python]Max Points on a Line/直线上最多的点数-蒲公英云

[Leetcode][python]Max Points on a Line/直线上最多的点数

- 日理万妓 2022-06-03 04:51 711阅读 0赞

题目大意

在一个平面上有n个点，求一条直线最多能够经过多少个这些点。

解题思路

哈希表保存斜率

代码

注意有个坑：
测试集[[0,0],[94911151,94911150],[94911152,94911151]]，由于数字大，直接内置除法斜率会算成一样的，用numpy库运算

import numpy as np
class Solution:
    def maxPoints(self, points):
        """
        :type points: List[Point]
        :rtype: int
        """
        n = len(points)
        slope_map = {}
        result = 0
        for i in range(n):
            # print(slope_map)
            slope_map.clear()
            same, vertical = 1, 0
            slope_max = 0
            for j in range(i + 1, n):
                dx, dy = points[i].x - points[j].x, points[i].y - points[j].y
                if dx == dy == 0:  # 同一个点
                    same += 1
                elif dx == 0:  # 斜率无限大，垂直
                    vertical += 1
                else:
                    slope = (dy * np.longdouble(1)) / dx
                    # slope = float(dy) / float(dx)
                    # print(slope)
                    slope_map[slope] = slope_map.get(slope, 0) + 1
                    slope_max = max(slope_max, slope_map[slope])
            result = max(result, max(slope_max, vertical) + same)
        return result