作者wangtrying (老王)
看板CSSE
标题[问题] 面试问到的问题...
时间Tue Dec 11 22:34:50 2012
在 XY 平面上,
给n个点 Pi = (Xi, Yi), i = 1...n,
找出最多点共线时 这条线上面的点的个数
怎麽解的漂亮啊?
小弟想得到的就是暴力法
每两个点算斜率 m
放到一个Dictionary的资料结构
key是m, value是出现次数...
所以 总共会计算 n(n-1)/2 次 m 值
然後再对Dictionary的value找最大值 就是解了
但是这样是O(n^2) 不知道大家有没有更好的做法?
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 114.24.44.237
1F：推 suhorng:这样做是 O(n^3) 喔, 计算出现次数要 n 12/11 22:37
2F：→ wangtrying:big O的话, n会被n^2盖掉吧? 还是我有误会你的意思? 12/11 22:46
3F：→ suhorng:找出最多点共线时线上的点数 所以位置不同 斜率相同的线 12/11 22:48
4F：→ suhorng:是不同的 12/11 22:48
5F：→ suhorng:所以粗估每个斜率有 n 种可能(n个点) 当然可能少於这数字 12/11 22:48
6F：→ wangtrying:ㄟ 不好意思 我可能没有把题目叙述得很好...orz 12/11 22:51
7F：→ wangtrying:我印象中他的意思应该是说 比如说 洒两个点在平面上 12/11 22:52
8F：→ wangtrying:那得到的值当然是2, 洒三个点, 而这三个点形成三角形 12/11 22:53
9F：→ wangtrying:那也是2, 但是说这三个点刚好共线的话, 那就是3了 12/11 22:53
10F：→ wangtrying:然後现在撒了n个点在平面上, 假如恰好有四点共线 12/11 22:55
11F：→ wangtrying:那就是4, 大概是这样啦... 12/11 22:55
12F：推 suhorng:可以考虑这样：现在 x=0 的线上有 10 个点 12/11 22:56
13F：→ suhorng:x=1 的线上有 11 个点 12/11 22:56
14F：→ suhorng:x=2 的线上有 13 个点 12/11 22:56
15F：→ suhorng:那计算共线时 x=0, x=1, x=2 这三条铅直线不会只算一次 12/11 22:58
16F：→ suhorng:或者说 斜率一样不代表他们贡献 12/11 22:59
17F：→ suhorng: 共线 12/11 22:59
18F：→ wangtrying:阿 我懂了 感谢suhorng大大 Y=mX+b, m跟b都要算出来 12/11 23:02
19F：推 wtvwtvwtv200:最快的做法应该是依序固定一个点，计算其他所有点 12/11 23:03
20F：→ wtvwtvwtv200:跟该点的斜率，然後用hash加速统计，O(n^2) 12/11 23:04
21F：→ wangtrying:斜率是不够的, 以suhorng大大的例子来说, 正确答案是13 12/11 23:06
22F：→ wangtrying:但是只算斜率的话 会得到34 就错了 12/11 23:06
23F：→ wangtrying:所以应该要用<m,b>的tuple当key, 丢到hash里面 12/11 23:08
24F：推 suhorng:hash是对的 就是枚举点然後转一圈 12/11 23:08
25F：→ suhorng:然後相对於这个点斜率相同的就是在同条线上 12/11 23:09
26F：→ wtvwtvwtv200:姆…我的意思是针对每个点分别计算跟其他点的斜率 12/11 23:09
27F：→ wangtrying:感谢wtvwtvwtv200跟suhorng两位大大 orz 12/11 23:09
28F：→ suhorng:看到推文了XD 差不多例子 12/11 23:09
29F：→ wangtrying:wtv大 的意思是说 每转一圈就纪录斜率出现次数的最大值 12/11 23:13
30F：→ wangtrying:这样好像比较漂亮喔 12/11 23:14
※ wangtrying:转录至看板 Prob_Solve 12/13 00:12