Max Points on a Line (Python)
kitt
posted @ 2014年2月12日 00:40
in LeetCode
, 1914 阅读
计算每两点之间的斜率,找最大值,要注意同一个坐标多次出现的情况。
# 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): length = len(points) if length < 3: return length res = -1 for i in xrange(length): slope = {'inf': 0} samePointNum = 1 for j in xrange(length): if i == j: continue if points[i].x == points[j].x and points[i].y != points[j].y: slope['inf'] += 1 elif points[i].x != points[j].x: k = 1.0 * (points[i].y - points[j].y) / (points[i].x - points[j].x) slope[k] = 1 if k not in slope else slope[k] + 1 else: samePointNum += 1 res = max(res, max(slope.values()) + samePointNum) return res