Fw: [問題] 面試問到的問題...
看板Prob_Solve (計算數學 Problem Solving)作者wangtrying (老王)時間12年前 (2012/12/13 00:12)推噓1(1推 0噓 3→)留言4則, 2人參與討論串1/8 (看更多)
※ [本文轉錄自 CSSE 看板 #1GnqICKG ]
作者: 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
推
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
※ 發信站: 批踢踢實業坊(ptt.cc)
※ 轉錄者: wangtrying (114.24.44.237), 時間: 12/13/2012 00:12:34
→
12/13 00:28, , 31F
12/13 00:28, 31F
→
12/13 00:29, , 32F
12/13 00:29, 32F
推
12/13 13:35, , 33F
12/13 13:35, 33F
→
12/13 13:36, , 34F
12/13 13:36, 34F
討論串 (同標題文章)
完整討論串 (本文為第 1 之 8 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
