题目:
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
题解:
这道题就是给你一个2D平面,然后给你的数据结构是由横纵坐标表示的点,然后看哪条直线上的点最多。
(1)两点确定一条直线
(2)斜率相同的点落在一条直线上
(3)坐标相同的两个不同的点 算作2个点
利用HashMap,Key值存斜率,Value存此斜率下的点的个数。同时考虑特殊情况,如果恰巧遍历到一个相同坐标的点,那么就维护一个local的counter来记录相同的点。
维护一个localmax,计算当前情况下的最大值;再维护一个全局Max来计算总的最大值。
返回全局Max即可。
代码如下:
Reference:
http://blog.csdn.net/ttgump/article/details/23146357
http://blog.csdn.net/linhuanmars/article/details/21060933
Max Points on a Line leetcode java,布布扣,bubuko.com
Max Points on a Line leetcode java
原文:http://www.cnblogs.com/springfor/p/3896120.html