給好多點你，然后求出最多的點處于同一條直線，就是暴力，然后用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; }};新聞熱點
疑難解答
