美文网首页
149. Max Points on a Line

149. Max Points on a Line

作者: juexin | 来源:发表于2017-01-09 19:17 被阅读0次

    Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

    class Solution {
    public:
        int maxPoints(vector<Point>& points) {
            unordered_map<float,int> mp;
            int maxNum = 0;
            for(int i=0;i<points.size();i++)
            {
                mp.clear();
                mp[INT_MAX] = 0; //当只有一个元素时,这个赋值有用
                int duplicate = 1;
                for(int j=0;j<points.size();j++)
                {
                    if(j==i)
                      continue;
                    if(points[i].x == points[j].x&&points[i].y == points[j].y)
                    {
                        duplicate++;
                        continue;
                    }
                    float k = points[i].x == points[j].x ?  INT_MAX : (float)(points[i].y - points[j].y)/(points[i].x - points[j].x);
                    mp[k]++;
     
                }
                unordered_map<float,int>::iterator it = mp.begin();
                for(;it!=mp.end();it++)
                {
                  if(it->second + duplicate > maxNum)
                    maxNum = it->second + duplicate;
                }
            }
            return maxNum;
        }
    };
    

    相关文章

      网友评论

          本文标题:149. Max Points on a Line

          本文链接:https://www.haomeiwen.com/subject/hiphbttx.html