读书人

微软的一道比较难的算法面试题,该如何

发布时间: 2012-03-21 13:33:14 作者: rapoo

微软的一道比较难的算法面试题
平面上N个点,没两个点都确定一条直线,求出斜率最大的那条直线所通过的两个点(斜率不存在的情况不考虑)。时间效率越高越好

[解决办法]
先把N个点按x排序。
斜率k最大值为max(斜率(point[i],point[i+1])) 0<=i<n-2。
复杂度Nlog(N)。

读书人网 >软件架构设计

热点推荐