这道题属于计算几何的题目，要求给定一个点集合，是求出最多点通过一条直线的数量。我的思路是n个点总共构成n*(n-1)/2条直线，然后对每条直线看看是有多少点在直线上，记录下最大的那个，最后返回结果。而判断一个点p_k在p_i, p_j构成的直线上的条件是(p_k.y-p_i.y)*(p_j.x-p_i.x)==(p_j.y-p_i.y)*(p_k.x-p_i.x)。算法总共是三层循环，时间复杂度是O(n^3),空间复杂度则是O(1),因为不需要额外空间做存储。代码如下：
public int maxPoints(Point[] points) {
if(points==null || points.length==0)
{
return 0;
}
if(allSamePoints(points))
return points.length;
int max = 0;
for(int i=0;i
大家看到代码中还写了一个allSamePoints的函数，这是一个非常corner的情况，就是所有点都是一个点的情况，因为下面我们要跳过重复的点（否则两个重合点会认为任何点都在他们构成的直线上），但是偏偏当所有点都重合时，我们需要返回所有点。除了这种情况，只要有一个点不重合，我们就会从那个点得到结果，这是属于比较tricky的情况。
计算几何的题目在现在的面试中挺常见的，可能因为有些问题比较实用的缘故，而且实现中一般细节比较多，容易出bug，所以还是得重视。如果有朋友有更好的解法或者思路，欢迎交流哈，可以留言或者发邮件到linhuanmars@gmail.com给我。