给定一个二维平面,平面上有 n 个点,求最多有多少个点在同一条直线上。
https://leetcode-cn.com/problems/max-points-on-a-line/
class Point:
def __init__(self, a=0, b=0):
self.x = a
self.y = b
class Solution:
def maxPoints(self, points):
size = len(points)
if size in [0,1]:
return size
res = 0
for i in range(size):
cur_max = 1
d = {}
count = 0
dup = 0
for j in range(size):
if j!=i:
deta_x = points[i].x - points[j].x
deta_y = points[i].y - points[j].y
if deta_x == 0 and deta_y == 0:
dup += 1
elif deta_x == 0:
if count == 0:
count = 2
else:
count += 1
cur_max = max(count,cur_max)
else:
k = deta_y/deta_x
if d.get(k) == None:
d[k] = 2
else:
d[k] += 1
cur_max = max(d[k],cur_max)
res = max(res,cur_max + dup)
return res
网友评论