给定一个二维平面,平面上有 n 个点,求最多有多少个点在同一条直线上。
示例 1:
输入: [[1,1],[2,2],[3,3]]
输出: 3
解释:
^
|
| o
| o
| o
+------------->
0 1 2 3 4
示例 2:
输入: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
输出: 4
解释:
^
|
| o
| o o
| o
| o o
+------------------->
0 1 2 3 4 5 6
这道题很自然就能想到计算斜率,哈希表存储,但是需要注意几个点:
1、斜率无穷大的特殊情况
2、有相同点的情况
3、特殊测试用例:[[0,0],[94911151,94911150],[94911152,94911151]] 浮点数精度不够
解决方案:
1、哈希表加一个键
2、用same存储相同点的个数
3、用dx/dy代替dy/dx可以去除这种浮点数精度不够的情况,但只是针对这一个样例;另一个方法:使用Decimal。
from decimal import Decimal
Decimal((point[1][1] - point[0][1]))/Decimal((point[1][0] - point[0][0]))
牺牲了一些计算上的耗时。
完整代码:
class Solution(object):
def maxPoints(self, points):
"""
:type points: List[List[int]]
:rtype: int
"""
length = len(points)
if length < 3: return length
max_points = 0
for i in range(length):
d = {'inf':0}
same = 1
for j in range(i,length):
if i == j:
continue
if points[i][1] == points[j][1] and points[i][0] != points[j][0]:
d['inf'] += 1
elif points[i][0] != points[j][0]:
k = 1.0 * (points[i][0] - points[j][0])/(points[i][1] - points[j][1])
if k not in d:
d[k] = 1
else:
d[k] += 1
else:
same += 1
max_points = max(max_points, max(d.values()) + same)
return max_points