149. Max Points on a Line

2019-11-08 03:20:35

字体：大中小

来源：转载

供稿：网友

给好多点你，然后求出最多的点处于同一条直线，就是暴力，然后用map记录 Ps 如果是垂直的话，k是INT_MAX，有可能有很多点是同一点，不要重复判断

/** * 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; int size = points.size(); if(size < 3) return size; int maxx = 0; map<double, int>ma; for(int i = 0; i < size; ++ i){ ma.clear(); int num = 1; ma[INT_MIN] = 0; for(int j = 0; j < size; ++ j){ if(i == j) continue; if(points[i].x == points[j].x && points[i].y == points[j].y){ num++; continue; } else{ double k = (points[i].x == points[j].x) ? INT_MAX : (double)(points[i].y - points[j].y) / (points[i].x - points[j].x); ma[k]++; } } auto iter = ma.begin(); for(; iter != ma.end(); ++ iter){ if(iter -> second + num > maxx) maxx = iter -> second + num; } } return maxx; }};

上一篇：Pots——广度优先搜索+结构体数组

下一篇：148. Sort List