Lintcode186 Max Points on a Line solution 题解
发布在lintcode2018年1月25日view:277
在文章任何区域双击击即可给文章添加【评注】!浮到评注点上可以查看详情。

【题目描述】

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

给出二维平面上的n个点,求最多有多少点在同一条直线上。

【题目链接】

www.lintcode.com/en/problem/max-points-on-a-line/

【题目解析】

(1)两点确定一条直线

(2)斜率相同的点落在一条直线上

(3)坐标相同的两个不同的点 算作2个点

使用Hashmap来存放键值对,Key用来存放斜率,value存放该斜率下的点的个数,对每个点进行循环遍历,计算该点和其余各个点的斜率,然后更新Hashmap中对应的值,每个点都计算出点数最大的值,保存在局部变量localmax中,维护一个全局变量max来存放最后的结果。

【参考答案】

www.jiuzhang.com/solutions/max-points-on-a-line/

作者:程风破浪会有时 链接:https://www.jianshu.com/p/3002df8ddf53 來源:简书 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

评论
发表评论
暂无评论
WRITTEN BY
PUBLISHED IN
lintcode

lintcode题解

我的收藏