题目:
Given n points
on a 2D plane, find the maximum number of points that lie on the same straight line
第一种解法:
最简单最粗暴的解法就是利用多重遍历去解决这种问题,从第一个点开始,和其后的每一个点组成一条线,然后在遍历其中的每一个点是否在这条线上。这种方法简单粗暴,显而易见带来的负面效果是算法的时间复杂度比较高,O(n3)的时间复杂度。在这个算法中注意的是,如果用来求线的两个点相同或者导致ax+by+c=0中的系数都为0的话,这种情况要另行考虑,这样可以避免漏掉这种情况。
解题代码:
#include <iostream> #include <vector> using namespace std; class Solution { public: int maxPoints(vector<Point> &points) { if(points.size()<=2) return points.size(); int max = 2; for(int i=0;i<points.size();i++){ for(int j=i+1;j<points.size();j++){ //计算出ax+by+c=0这条线的参数 int a = points[j].y - points[i].y; int b = points[i].x - points[j].x; int c = points[j].x*points[i].y - points[i].x*points[j].y; int count = 0; for(int k=0;k<points.size();k++){ if(a==0&&b==0){ if(points[k].y==points[j].y&&points[k].x==points[j].x) count++; continue; } if((a*points[k].x + b*points[k].y+c)==0) count++; } if(count>max) max= count; } } return max; } };
代码运行时间为:
下面寻求第二种解法:
(想法来源csdn博客,博主dancingrain),http://blog.csdn.net/doufei_ccst/article/details/22177193
2.对于每一个点A,计算其与剩下所有点的连线的斜率。然后对斜率进行排序,从中找出出现次数最多的,作为经过点A的共线的点的最大个数。
对于每一个点都做同样的操作,最后就可以得到为题的解。 其时间复杂度是O(N^2logN),如果把对斜率的排序算法换成hash,就可以进一步提高时间效率,达到O(N^2).
这里使用的是C++自带的排序算法,该排序默认的是升序。
#include <vector> #include <iostream> #include <algorithm> #include <fstream> using namespace std; const double INF=210000000; /** * Definition for a point. struct Point { int x; int y; Point() : x(0), y(0) {} Point(int a, int b) : x(a), y(b) {} }; */ class Solution { public: int maxPoints(vector<Point> &points) { if(points.size()<=2) return points.size(); int max = 0; bool flag = false; for(int i=0;i<points.size()-1;i++){ vector<double> k; int mer=0; //这里有一个去重的问题 for(int j=i+1;j<points.size();j++){ if((points[i].x == points[j].x)&&(points[j].y==points[i].y)) mer++; else if(points[i].x == points[j].x) { k.push_back(INF); } else{ k.push_back((double)(points[j].y-points[i].y)/(double)(points[j].x-points[i].x)); } } sort(k.begin(),k.end()); if(k.size()==0 &&max<points.size()) { max += 1; max += mer; return max; } for(int m=0;m<k.size();m++) { int counter =1; while(m+1<k.size() && k[m]==k[m+1]) { m++; counter++; } if(counter>=(max)){ flag = true; max=counter+1; } } //这里多加了几次 if(flag){ max += mer; flag = false; } } return max; } };
这样算法的性能确实提高了,时间复杂度也变为了O(N^2logN),这个真是提高很大啊。
解法三:
将解法二中的排序算法换成hash,应为hash的时间复杂度为O(1),这样,可以讲时间复杂度提高到O(N2)了,这也许是最好的解法了。目前还没发现更好解法,个人能力也有限啊。最近真是各种受打击,需要好好学些了