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に使用します.
例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