当前位置: 首页 > 面试 > 正文

微软面试题(二)

关键字:
1 星2 星3 星4 星5 星 (2 次投票, 评分: 5.00, 总分: 5)
Loading ... Loading ...
baidu_share

2、平面上N个点,没两个点都确定一条直线,求出斜率最大的那条直线所通过的两个点

平面上N个点,没两个点都确定一条直线,求出斜率最大的那条直线所通过的两个点(斜率不存在的情况不考虑)。时间效率越高越好。
先把N个点按x排序。
斜率k最大值为max(斜率(point[i],point[i+1])) 0 <=i 复杂度Nlog(N)。
以3个点为例,按照x排序后为ABC,假如3点共线,则斜率一样,假如不共线,则可以证明AB或BC中,一定有一个点的斜率大于AC,一个点的斜率小于AC。

本文固定链接: http://www.chepoo.com/microsoft-interview-two.html | IT技术精华网

【上一篇】
【下一篇】

微软面试题(二):等您坐沙发呢!

发表评论