google面试题（二）

平面上N个点，求一条直线，穿过的点数最多

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

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

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

评论

1 楼 LinuxFans 2008-02-11  

数学问题啊，这NB的公司就是不一样啊.