186-最多有多少个点在一条直线上
思路
从第一个开始，求出此点与其它点的斜率（注意斜率会可能会不存在），斜率相同的点在同一直线上，相同的点（重复出现的点）与任何点均在同一直线上
为了遍历方便，使用 map 保存斜率与点数的映射关系
code
/**
* 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:
/**
* @param points an array of point
* @return an integer
*/
int maxPoints(vector<Point>& points) {
// Write your code here
int size = points.size();
if (size <= 0) {
return 0;
}
map<double, int> map;
int maxPoints = 0;
for (int i = 0; i < size; i++) {
map.clear();
int samek = 0, maxk = 0;
for (int j = 0; j < size; j++) {
// 同一点
if (points[i].x == points[j].x && points[i].y == points[j].y) {
samek++;
}
// 斜率不存在
else if (points[i].x == points[j].x && points[i].y != points[j].y) {
maxk++;
}
// 斜率存在
else {
double k = double(points[i].y - points[j].y) / double(points[i].x - points[j].x);
map[k]++;
}
}
std::map<double, int>::iterator it;
for (it = map.begin(); it != map.end(); it++) {
maxPoints = maxPoints > it->second + samek ? maxPoints : it->second + samek;
}
maxPoints = maxPoints > maxk + samek ? maxPoints : maxk + samek;
}
return maxPoints;
}
};