也找到了一个AC的做法，明天研究
# Definition for a point.
# class Point(object):
# def __init__(self, a=0, b=0):
# self.x = a
# self.y = b
import random
import collections
class Solution(object):
def maxPoints(self, points):
if len(points)==0: #case for 0 inputs
return 0
if len(points)==1: # case for just one point
return 1
xls=[]
yls=[]
for ii in range(0,len(points)): # case for all the points are same
xls.append(points[ii].x)
yls.append(points[ii].y)
xset=set(xls)
yset=set(yls)
if len(xset)==1 and len(yset)==1:
return len(points)
max_points=0
for i in range (0,100):
[p1,p2]=random.sample(range(len(points)), 2) # randomly choose two points
while(points[p1].x==points[p2].x and points[p2].y==points[p1].y ): #make sure two points are different
[p1,p2]=random.sample(range(len(points)), 2)
X1=points[p1].x
X2=points[p2].x
Y1=points[p1].y
Y2=points[p2].y
A = Y2 - Y1
B = X1 - X2
C=X2*Y1 - X1*Y2 #define the parameters of the line
temp_num=0
for j in range(0,len(points)):
X=points[j].x
Y=points[j].y
if A*X+B*Y+C==0: # the error must be 0 to make sure the point is in the line
temp_num=temp_num+1
if temp_num > max_points:
max_points=temp_num
return max_points
这其实不是一个完美的做法，因为有随机性在里面，过leetcode没问题但不能保证其他，所以，还是遍历最靠谱，改了一下，代码如下：
# Definition for a point.
# class Point(object):
# def __init__(self, a=0, b=0):
# self.x = a
# self.y = b
import random
import collections
class Solution(object):
def maxPoints(self, points):
if len(points)==0: #case for 0 inputs
return 0
if len(points)==1: # case for just one point
return 1
xls=[]
yls=[]
for ii in range(0,len(points)): # case for all the points are same
xls.append(points[ii].x)
yls.append(points[ii].y)
xset=set(xls)
yset=set(yls)
if len(xset)==1 and len(yset)==1:
return len(points)
max_points=0
for p1 in range(len(points) - 1):
for p2 in range(p1, len(points)):
if points[p1].x==points[p2].x and points[p2].y==points[p1].y: #make sure two points are different
continue
X1=points[p1].x
X2=points[p2].x
Y1=points[p1].y
Y2=points[p2].y
A = Y2 - Y1
B = X1 - X2
C=X2*Y1 - X1*Y2 #define the parameters of the line
temp_num=0
for j in range(0,len(points)):
X=points[j].x
Y=points[j].y
if A*X+B*Y+C==0: # the error must be 0 to make sure the point is in the line
temp_num=temp_num+1
if temp_num > max_points:
max_points=temp_num
return max_points
