暴力解法

返回首页

返回算法分类分析

第一题 Max Points on a Line

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

解法

这一通过

if p1.x == p2.x:
                t = (float('inf'), p1.x)
            else:
                t = ((p1.y-p2.y)/float(p1.x-p2.x), (p1.x*p2.y-p2.x*p1.y)/float(p1.x-p2.x))

来确定一条线。另外对defaultdict的使用也值得学习。

class Solution(object):
def maxPoints(self, points):
    d = collections.defaultdict(list)
    for i in range(1, len(points)):
        for j in range(i):
            p1, p2 = points[i], points[j]
            if p1.x == p2.x:
                t = (float('inf'), p1.x)
            else:
                t = ((p1.y-p2.y)/float(p1.x-p2.x), (p1.x*p2.y-p2.x*p1.y)/float(p1.x-p2.x))
            d[t] += [p1, p2]
    return max(len(set(l)) for l in d.values()) if len(points)>1 else len(points)