注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex149 Max Points on a Line  

2015-05-31 17:06:10|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

暴力搜索,每次计算一个点和所有点的斜率,一样的抽出来,不过需要注意斜率无穷和重复点的情况。得到的结果用map保存

/*
* 这个题的解法好傻啊!
* 直接计算每个点和别的点的斜率然后统计最大数量
* 我真不知道这个题的为什么那么小的提交成功率
* http://www.cnblogs.com/easonliu/p/4527792.html
*/
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) {
int res = 0, same_cnt, ver_cnt, cnt;
unordered_map<double, int> mp;
double k;
for (int i = 0; i < points.size(); ++i)
{
same_cnt = 0; //和i重复的点
ver_cnt = 0;
cnt = 0; //计算最大数量
mp.clear();
for (int j = 0; j < points.size(); ++j)
{
if (points[i].x == points[j].x)
{
//需要考虑x相同,斜率无穷大的情况
if (points[i].y == points[j].y)
{
++same_cnt; //重复的点
continue;
}
else
{
++ver_cnt;
//斜率无穷大点计数
cnt = max(cnt, ver_cnt);
}
}
else
{
//计算斜率,然后map映射是斜率和数量
k = (double)(points[i].y - points[j].y) / (points[i].x - points[j].x);
++mp[k];
cnt = max(cnt, mp[k]);
}
}
//因为最后还需要考虑重复的点
res = max(res, cnt + same_cnt);
}
return res;
}
};


  评论这张
 
阅读(9)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017