作者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