首页 > 代码库 > 【leetcode】Max Points on a Line
【leetcode】Max Points on a Line
题目:给定二维坐标上的若干点,找出这样一条线,属于该线的点数最多,返回点数。
分析:两个点确定了一条直线。共线,说明斜率相同。那么确定一个点A,该点与其他的点就会生成不同的斜率。这些斜率中,会存在相同的,那么这些相同的斜率就说明他们跟A在同一条直线上。
这里我们把斜率分成两种,一种是正常的斜率,就是可以写成 y = kx + b形式的k;一种就是横坐标相同,纵坐标不相同的,这时的斜率为无穷大。
给定的点中,肯定会存在重复的点,我们把它称为称为“重数”(笔者临时起的名字,数学上不存在),那么以某个点为起点,计算出的斜率相同(共线)的点数时,要加上该点的重数。
最后,我们取以上两种斜率所确定的点中,点数最多的。
int maxPoints(vector<Point> &points) { int len = points.size(); if(len < 1) return 0; int maxPoint = 1; unordered_map<double, int> slops_map; for (int i = 0; i < len - 1; ++i) { slops_map.clear(); //the number of points which just has the same x coordinate int num_infinit = 1; //the same point as points[i]. int num_same = 0; //most number of points which in the same normal slop line. int slop_max = 0x80000000; for (int j = i + 1; j < len; ++j) { //same points if(points[i].x == points[j].x && points[i].y == points[j].y) { num_same++; continue; } //vertical, which the slop is infinit. else if(points[i].x == points[j].x) num_infinit++; // normal slop else { double cur_slop = (points[i].y - points[j].y)/(points[i].x - points[j].x + 0.0); if(slops_map.find(cur_slop) != slops_map.end()) slops_map[cur_slop]++; else slops_map[cur_slop] = 2; if(slop_max < slops_map[cur_slop]) slop_max = slops_map[cur_slop]; } } maxPoint = max(max(num_infinit, slop_max + num_same), maxPoint); } return maxPoint; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。