Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
先上代碼
/**
* 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() == 0)
return 0;
if (points.size() == 1)
return 1;
int result = 0;
double k;
for (int i = 0;i < points.size();i++){
map<double,int> kMap;
int reCount = 0;//重復(fù)的點(diǎn)
int vCount = 1;//豎直的計(jì)數(shù)
int currentMax = 1;//當(dāng)前最大值存儲(chǔ)
for (int j = i+1;j < points.size();j++){
if (points[i].x == points[j].x && points[i].y == points[j].y){
reCount++;
}else{
if (points[i].x == points[j].x){
vCount++;
currentMax = max(currentMax,vCount);
}else{
k = 1.0 * (points[j].y-points[i].y) / (points[j].x-points[i].x);
if (kMap[k] == 0)
kMap[k] = 2;
else
kMap[k]++;
}
}
currentMax = max(kMap[k],currentMax);
}
result = max(result,currentMax+reCount);
}
return result;
}
};
按照給出的提示悼沈，本題采用的是窮舉的思路拼岳。
將所有的情況列舉出來，這條占點(diǎn)最多的線自然就求出來了乘综。
1符隙、首先趴捅，我們將0個(gè)點(diǎn)和1個(gè)點(diǎn)的情況篩選出來
2、考慮共線的條件：{
斜率相等
豎直
兩點(diǎn)相同
}
3霹疫、循環(huán)走起??
