本文共 1302 字,大约阅读时间需要 4 分钟。
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
Subscribe to see which companies asked this question
思路
给出平面上的几个点,求出同在一条直线上的点最多的个数 两个for循环,求两个点之间的斜率,注意垂直于x轴的斜率的表示以及覆盖点的个数[0,0]和[0,0]是两个点
class Point(object): def __init__(self,a=0,b=0): self.x=a self.y=bclass Solution(object): def maxPoints(self,points): Lenth=len(points) if not Lenth: return 0 Max_=0 for i in range(Lenth-1): dict={} count=0 for j in range(i+1,Lenth): if points[i].x-points[j].x==0: if points[i].y==points[j].y: count=count+1 dict.setdefault('b',0) else: if 'a' not in dict: dict.setdefault('a',1) else: dict['a']=dict['a']+1 else: k=(points[j].y-points[i].y)*1.0/(points[j].x-points[i].x) if k not in dict: dict.setdefault(k,1) else: dict[k]=dict[k]+1 #print dict Max_=max(Max_,max(dict.items(),key=lambda x:x[1])[1]+count) return (Max_+1)
转载地址:http://gwqmi.baihongyu.com/