[問題] 面試問到的問題...
在 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
推
12/11 22:37, , 1F
12/11 22:37, 1F
→
12/11 22:46, , 2F
12/11 22:46, 2F
→
12/11 22:48, , 3F
12/11 22:48, 3F
→
12/11 22:48, , 4F
12/11 22:48, 4F
→
12/11 22:48, , 5F
12/11 22:48, 5F
→
12/11 22:51, , 6F
12/11 22:51, 6F
→
12/11 22:52, , 7F
12/11 22:52, 7F
→
12/11 22:53, , 8F
12/11 22:53, 8F
→
12/11 22:53, , 9F
12/11 22:53, 9F
→
12/11 22:55, , 10F
12/11 22:55, 10F
→
12/11 22:55, , 11F
12/11 22:55, 11F
推
12/11 22:56, , 12F
12/11 22:56, 12F
→
12/11 22:56, , 13F
12/11 22:56, 13F
→
12/11 22:56, , 14F
12/11 22:56, 14F
→
12/11 22:58, , 15F
12/11 22:58, 15F
→
12/11 22:59, , 16F
12/11 22:59, 16F
→
12/11 22:59, , 17F
12/11 22:59, 17F
→
12/11 23:02, , 18F
12/11 23:02, 18F
推
12/11 23:03, , 19F
12/11 23:03, 19F
→
12/11 23:04, , 20F
12/11 23:04, 20F
→
12/11 23:06, , 21F
12/11 23:06, 21F
→
12/11 23:06, , 22F
12/11 23:06, 22F
→
12/11 23:08, , 23F
12/11 23:08, 23F
推
12/11 23:08, , 24F
12/11 23:08, 24F
→
12/11 23:09, , 25F
12/11 23:09, 25F
→
12/11 23:09, , 26F
12/11 23:09, 26F
→
12/11 23:09, , 27F
12/11 23:09, 27F
→
12/11 23:09, , 28F
12/11 23:09, 28F
→
12/11 23:13, , 29F
12/11 23:13, 29F
→
12/11 23:14, , 30F
12/11 23:14, 30F
※ wangtrying:轉錄至看板 Prob_Solve 12/13 00:12
CSSE 近期熱門文章
PTT數位生活區 即時熱門文章