## [Leetcode]Max Points on a Line 作者是 在线疯狂 发布于 2014年10月16日 在 LeetCode, Python.

### 题目描述

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

### Python代码如下：

``````# Definition for a point
# 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):
ans = 0
size = len(points)
for x in range(size):
k_dict = {}
same = 0
for y in range(x + 1, size):
if self.isEqual(points[x], points[y]):
same += 1
else:
k = self.getK(points[x], points[y])
if k_dict.get(k) is None:
k_dict[k] = 1
else:
k_dict[k] += 1
val = 0
if len(k_dict):
val = max(k_dict.values())
ans = max(ans, val + same + 1)
return ans
def getK(self, pa, pb):
if pa.x == pb.x:
return None
return 1.0 * (pb.y - pa.y) / (pb.x - pa.x)
def isEqual(self, pa, pb):
return pa.x == pb.x and pa.y == pb.y``````

Pingbacks已关闭。

1. 书影网友 发布于 2017年6月29日 02:40 #

This solution can be improved to O(n^2) using hash table to store the slope. However, the extra caution to the precision problem.