首页 > 代码库 > 【leetcode】Max Points on a Line
【leetcode】Max Points on a Line
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.
解题思路:
1.首先由这么一个O(n^3)的方法,也就是算出每条线的方程(n^2),然后判断有多少点在每条线上(N)。这个方法肯定是可行的,只是复杂度太高
2.然后想到一个O(N)的,对每一个点,分别计算这个点和其他所有点构成的斜率,具有相同斜率最多的点所构成的直线,就是具有最多点的直线。
注意的地方:
1.重合的点
2.斜率不存在的点
1 # Definition for a point 2 class Point: 3 def __init__(self, a=0, b=0): 4 self.x = a 5 self.y = b 6 7 class Solution: 8 # @param points, a list of Points 9 # @return an integer10 def calcK(self,pa, pb):11 t = ((pb.y - pa.y) * 1.0) / (pb.x - pa.x)12 return t13 14 def maxPoints(self, points):15 l = len(points)16 res = 017 if l <= 2:18 return l 19 for i in xrange(l):20 same = 021 k = {}22 k[‘inf‘] = 023 for j in xrange(l):24 if points[j].x == points[i].x and points[j].y != points[i].y:25 k[‘inf‘] += 126 elif points[j].x == points[i].x and points[j].y == points[i].y:27 same +=128 else:29 t = self.calcK(points[j],points[i])30 if t not in k.keys():31 k[t] = 132 else:33 k[t] += 134 res = max(res, max(k.values())+same)35 return res36 37 def main():38 points = []39 points.append(Point(0,0))40 points.append(Point(1,1))41 points.append(Point(1,-1))42 #points.append(Point(0,0))43 #points.append(Point(1,1))44 #points.append(Point(0,0))45 s = Solution()46 print s.maxPoints(points)47 48 49 if __name__ == ‘__main__‘:50 main()51
【leetcode】Max Points on a Line
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。