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），然后判斷有多少點(diǎn)在每條線上（N）。這個方法肯定是可行的，只是復(fù)雜度太高
2.然后想到一個O(N)的，對每一個點(diǎn)，分別計(jì)算這個點(diǎn)和其他所有點(diǎn)構(gòu)成的斜率，具有相同斜率最多的點(diǎn)所構(gòu)成的直線，就是具有最多點(diǎn)的直線。

注意的地方：

1.重合的點(diǎn)
2.斜率不存在的點(diǎn)

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

?

轉(zhuǎn)載于:https://www.cnblogs.com/MrLJC/p/4118069.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的【leetcode】Max Points on a Line的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。