【leetcode】MaxPointsonaLine

2019-11-14 17:29:22

字體：大中小

來源：轉載

供稿：網友

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