leetcode No149. Max Points on a Line

本文主要是介绍leetcode No149. Max Points on a Line，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Question:

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
求二维坐标中，最多共线的点数

Algorithm

遍历每个点，找到斜率一样的点，用哈希表存储大小
注意：
相同的点单独计算
在同一竖线上斜率无穷大，可以记为INT_MAX

Accepted 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:int maxPoints(vector<Point>& points) {if(points.size()<3)return points.size();int res=0;for(int i=0;i<points.size();i++){int samePointNum=0;unordered_map<double,int> hash;int maxPointNum=1;for(int j=0;j<points.size();j++){if(i==j)continue;if((points[i].x == points[j].x) && (points[i].y == points[j].y))   //同一个点samePointNum++;else if(points[i].x == points[j].x)   //在同一竖线上hash[INT_MAX]++;else{double delta=(double)(points[j].y-points[i].y)/(points[j].x-points[i].x);hash[delta]++;}}unordered_map<double,int>::iterator it=hash.begin();for (; it != hash.end(); it++){if (maxPointNum < (it->second+1))maxPointNum = (it->second+1);}		maxPointNum+=samePointNum;if(res<maxPointNum)res=maxPointNum;}return res;}
};