Friday, September 19, 2014

Leetcode: Max Points on a Line @Python

# Definition for a point
# class Point:
#     def __init__(self, a=0, b=0):
#         self.x = a
#         self.y = b

class Solution:
    # @param points, a list of Points
    # @return an integer
    def maxPoints(self, points):
        if len(points)==0: return 0
        n=len(points)
        maxnum=1
        for i in range(n):
            dic={'inf':0}
            same=0
            for j in range(n):
                if points[i].x==points[j].x and points[i].y==points[j].y:
                    same+=1
                else:
                    slope='inf' if points[i].x==points[j].x else 1.0*(points[i].y-points[j].y)/(points[i].x-points[j].x)
                    if slope not in dic:
                        dic[slope]=1
                    else:
                        dic[slope]+=1
            maxnum=max(maxnum,max(dic.values())+same)
        return maxnum

No comments :

Post a Comment