leetcode-Max Points on a Line
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
标题:平面上のいくつかの点の(x,y)座標を与えて、1本の直線を求めて、この直線の上の点は最も多くて、この最大の点数を返します
分析:この問題はアルゴリズムと細部が少し難しい問題だと感じて、通過率は10%しかありません.
アルゴリズム:
O(n^2)方法:まず各繰返し点の個数を統計し、複雑度が最大であるO(n*logn)を統計し、次に、各点について、他の点との傾きを計算し、map<傾き、個数>で直線上の点数を統計する.
傾きのkeyが当を選択すれば,O(1)で同じ傾きのkeyが見つかることを保証し,全体的な複雑度はO(n^2)である.
詳細:
1、空のセットと単点に注意して、空のセットは0を返して、単点は1を返します
2、ここのmapのkeyは傾きですが、doubleの精度の問題でkeyができないので、傾き*10^6を再整頓してlong longで格納し、keyとします
3、unodered_mapはkeyがpair、すなわちunordered_をサポートしません.map,int>不正
4、pair要素へのアクセス方法:pairpr,アクセス用pr.first,pr.second
コード:
标题:平面上のいくつかの点の(x,y)座標を与えて、1本の直線を求めて、この直線の上の点は最も多くて、この最大の点数を返します
分析:この問題はアルゴリズムと細部が少し難しい問題だと感じて、通過率は10%しかありません.
アルゴリズム:
O(n^2)方法:まず各繰返し点の個数を統計し、複雑度が最大であるO(n*logn)を統計し、次に、各点について、他の点との傾きを計算し、map<傾き、個数>で直線上の点数を統計する.
傾きのkeyが当を選択すれば,O(1)で同じ傾きのkeyが見つかることを保証し,全体的な複雑度はO(n^2)である.
詳細:
1、空のセットと単点に注意して、空のセットは0を返して、単点は1を返します
2、ここのmapのkeyは傾きですが、doubleの精度の問題でkeyができないので、傾き*10^6を再整頓してlong longで格納し、keyとします
3、unodered_mapはkeyがpair、すなわちunordered_をサポートしません.map
4、pair要素へのアクセス方法:pair
コード:
/**
* 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.empty()) return 0;
map<pair<int,int>,int> cnt;
for(int i=0; i<points.size(); i++)
{
pair<int,int> pr(points[i].x,points[i].y);
if(cnt.find(pr)==cnt.end()) cnt[pr] = 1;
else cnt[pr]++;
}
unordered_map<long long,int> mp;
int ans = 1;
for(auto p=cnt.begin(); p!=cnt.end(); p++)
{
int x = p->first.first;
int y = p->first.second;
int v = p->second;
if(v>ans) ans = v;
mp.clear();
for(auto q=cnt.begin(); q!=cnt.end(); q++)
{
if(p==q) continue;
int nx = q->first.first;
int ny = q->first.second;
int nv = q->second;
long long key;
if(x==nx) key = INT_MAX;
else key = (long long)(y-ny)*1000000/(x-nx);
if(mp.find(key)==mp.end()) mp[key] = v+nv;
else mp[key] += nv;
if(mp[key]>ans) ans = mp[key];
}
}
return ans;
}
};