LeetCode--Max Points on a Line

思路：

时间复杂度：O（n^2），挨个遍历。暴力搜索。

但是有几点要注意：第一，map的斜率是float，所以，为了不损失精度，求斜率先把int-》float，再相除；

第二，注意处理为空和为0的情况。为1是返回0还是1，这个和面试官交流，leetcode上面是返回1

 1 /**
 2  * Definition for a point.
 3  * struct Point {
 4  *     int x;
 5  *     int y;
 6  *     Point() : x(0), y(0) {}
 7  *     Point(int a, int b) : x(a), y(b) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     int maxPoints(vector<Point> &points) {
13         // IMPORTANT: Please reset any member data you declared, as
14         // the same Solution instance will be reused for each test case.
15         map<float,int> mp;
16         int maxNum = 0;
17         int i,j;
18         for(i = 0 ; i < points.size() ; ++i)
19         {
20             mp.clear();
21             int dup =1;
22             mp[INT_MIN] = 0;//为了处理为1的情况
23             for(j = 0 ; j < points.size() ; ++j)
24             {
25                 if(i == j)
26                     continue;
27                 if(points[i].x == points[j].x && points[i].y == points[j].y)
28                 {
29                     dup++;
30                     continue;
31                 }
32                 float k = (points[i].x == points[j].x)?(INT_MAX):(float)(points[i].y-points[j].y)/(points[i].x-points[j].x);
33                 mp[k]++;
34             }
35             map<float,int>::iterator it = mp.begin();
36             while(it != mp.end())
37             {
38                 if(it->second + dup > maxNum)
39                     maxNum = it->second + dup;
40                 ++it;
41             }
42         }
43         return maxNum;
44     }
45 };