leetcode149. 直線上で最も多い点数

5348 ワード

2 D平面を与えて、平面の上でn個の点があって、最大でどれだけの点が同じ直線の上であることを求めます.
例1:入力:[[1,1],[2,2],[3,3]]出力:3例2:入力:[[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]出力:4
O(N²)の方法では、傾きを記録する辞書を作成し、繰り返し点を記録するパラメータがあることに注意し、最後に傾きを計算するときに精度を向上させてDecimalに使用します.
# Definition for a point.
# class Point:
#     def __init__(self, a=0, b=0):
#         self.x = a
#         self.y = b

class Solution:
    def maxPoints(self, points: List[Point]) -> int:
        res = 0
        for i, point1 in enumerate(points):
            oneline_dict, same = {}, 1  #     ,     
            for j, point2 in enumerate(points[i+1:]):
                if point1.x == point2.x and point1.y == point2.y:
                    same += 1
                    continue
                from decimal import Decimal  #     
                oneline = float('inf') if point1.x == point2.x\
                    else Decimal(point2.y-point1.y)/Decimal(point2.x-point1.x)
                oneline_dict[oneline] = oneline_dict.get(oneline, 0) + 1
            if res < same:
                res = same
            for k, v in oneline_dict.items():
                if v+same > res:
                    res = v+same
        return res