题目
给出二维平面上的n个点，求最多有多少点在同一条直线上。
样例
给出4个点：(1, 2), (3, 6), (0, 0), (1, 3)。
一条直线上的点最多有3个。
解题
直接暴力求解有问题，时间复杂度O(N3)，对其中的相同点没有处理，斜率为0，不存在也没有处理，找出运行不对
看到通过定义一个HashMap存储直线的斜率，存在相同的情况就+ 1 ，最后找到斜率个数最长的那个。
下面程序中已经有很多注释了。
/**
* Definition for a point.
* class Point {
* int x;
* int y;
* Point() { x = 0; y = 0; }
* Point(int a, int b) { x = a; y = b; }
* }
*/
public class Solution {
/**
* @param points an array of point
* @return an integer
*/
public int maxPoints(Point[] points) {
// Write your code here
if(points == null)
return 0;
int m = points.length;
if(m == 0)
return 0;
if( m <= 2)
return m;
int maxline = 0;
HashMap<Double,Integer> map = new HashMap<Double,Integer>();
for(int i = 0 ;i < m ; i ++){
map.clear();
// dup 是记录和当前点i相同的点的个数，注意这里不包括当前点 i
int dup = 0;
for(int j = i + 1; j < m ;j++){
// 出来相同的点
if(points[i].x == points[j].x && points[i].y == points[j].y){
dup ++;
continue;
}
// 处理斜率不存在的情况
double k = points[i].x==points[j].x ?Integer.MAX_VALUE:
(0.0+ points[i].y-points[j].y)/(points[i].x-points[j].x)*1.0; if(map.containsKey(k)){
map.put(k,map.get(k)+1); // 这里是新的j点，只需 + 1
}else{
map.put(k,2); // i j 两个点所在的直线，有两个点
}
}
// 全部相同的情况
if(map.size()==0){
// 需要加上当前点
maxline = Math.max(maxline,dup + 1 );
}else{
for(int tmp:map.values()){
if(tmp+dup>maxline)
maxline = tmp+dup; }
} }
return maxline;
}
}
Java Code
# Definition for a point.
# class Point:
# def __init__(self, a=0, b=0):
# self.x = a
# self.y = b class Solution:
# @param {int[]} points an array of point
# @return {int} an integer
def maxPoints(self, points):
# Write your code here
if points == None :
return 0
m = len(points)
if m <= 2:
return m
maxline = 0
for i in range(m):
dup = 1
d = {}
d['inf'] = 0
for j in range((i+1),m):
if points[i].x == points[j].x and points[j].y == points[i].y:
dup +=1
elif points[j].x == points[i].x:
d['inf'] += 1
else:
k = 1.0*(points[j].y - points[i].y)/(points[j].x - points[i].x)
if k in d:
d[k] += 1
else:
d[k] = 1
maxline = max( max(d.values()) + dup,maxline) return maxline
Python Code