生活随笔
收集整理的这篇文章主要介绍了
【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 integer
10 def calcK(self,pa, pb):
11 t = ((pb.y - pa.y) * 1.0) / (pb.x -
pa.x)
12 return t
13
14 def maxPoints(self, points):
15 l =
len(points)
16 res =
0
17 if l <= 2
:
18 return l
19 for i
in xrange(l):
20 same =
0
21 k =
{}
22 k[
'inf'] =
0
23 for j
in xrange(l):
24 if points[j].x == points[i].x
and points[j].y !=
points[i].y:
25 k[
'inf'] += 1
26 elif points[j].x == points[i].x
and points[j].y ==
points[i].y:
27 same +=1
28 else:
29 t =
self.calcK(points[j],points[i])
30 if t
not in k.keys():
31 k[t] = 1
32 else:
33 k[t] += 1
34 res = max(res, max(k.values())+
same)
35 return res
36
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
转载于:https://www.cnblogs.com/MrLJC/p/4118069.html
创作挑战赛新人创作奖励来咯，坚持创作打卡瓜分现金大奖
总结
以上是生活随笔为你收集整理的【leetcode】Max Points on a Line的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。
