Google面试题求解:平面上N个点,求一条直线,穿过的点数最多。

已邀请:
 
**思路:**
2点确定一条线,N个点共有n(n-1)/2条线,穿过的点数最多的直线,斜率相同的最多,因此只要找出相同斜率最多的点对集合,并且有公共点的即可 

**方法一:**
用上三角矩阵,矩阵里的值为任意两点的斜率,上三角矩阵用数组a表示。问题就转化为求数组中相同数最多的并且有公共点的数,方法参照“请把一个整形数组中重复的数字去掉”。 
时间复杂度0(n^2) 

**方法二:**
平面上N个点以及这N个点构成的无向图,边数n(n-1)/2,对图遍历(深度或广度),遍历到某个点node的时候,计算该点与它的前一个点的斜率r,用pr存储前一个点与它的前结点的斜率,如果pr!=r,则返回到node,继续遍历node的下一条边,如果斜率相等,则count++。如果找不到,则从一下结点开始遍历未访问过的节点。 
时间复杂度0(n^2) 
 

要回复问题请先登录注册