首页 > 代码库 > careercup-数学与概率 7.6
careercup-数学与概率 7.6
7.6 在二维平面上，有一些点，请找出经过点数最多的那条线。
解法：
类似于leetcode：Max Points on a Line
我们只需在任意两点之间“画”一条无限长的直线（也即不是线段），并利用散列表追踪哪条直线出现的次数最多。这种做法的时间复杂度O(n^2)，因为一共有n^2条线段。
通过将每一个点与除了自己之外的每一点求斜率（要注意相等和斜率不存在的情况），使用unorder_map中来插入k值，并对相同的k值进行累加，累加一次相当于增加该直线上的一个点。主要思想就是一条直线上的任意一点与其他点求得的k值都相等，因此，可以利用任意一点与其他每个点求斜率来计算求得的斜率上点的数量。
C++实现代码：
#include<iostream>#include<unordered_map>#include<vector>#include<climits>using namespace std;struct Point{ int x; int y; Point():x(0),y(0){} Point(int a,int b):x(a),y(b){}};int maxPoints(vector<Point> &points){ if(points.empty()) return 0; int n=points.size(); int i,j; int maxnum=0; unordered_map<double,int> mp; for(i=0;i<n;i++) { int duplicate=1; mp[INT_MAX]=0; mp.clear(); for(j=0;j<n;j++) { if(i==j) continue; if(points[i].x==points[j].x&&points[i].y==points[j].y) { duplicate++; continue; } double k=(points[i].x==points[j].x?INT_MAX:(double)(points[i].y-points[j].y)/(points[i].x-points[j].x)); mp[k]++; } auto mp_iter=mp.begin(); while(mp_iter!=mp.end()) { if(mp_iter->second+duplicate>maxnum) maxnum=mp_iter->second+duplicate; mp_iter++; } } return maxnum;}int main(){ vector<Point> vec={Point(0,0),Point(1,1),Point(2,2),Point(388,4),Point(6,3),Point(0,0)}; cout<<maxPoints(vec)<<endl;}
careercup-数学与概率 7.6
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。