→ shaopin:回答的人請記得要分析你的演算法複雜度 09/22 13:33
推 changyuheng:先畫球框出一個概量，再暴力法；用來回答面試夠嗎？ 09/22 13:50
→ shaopin:不夠:) 09/22 14:02
→ chunhsiang:有個線性求第k大的演算法 整體O(n) 09/22 16:47
→ chunhsiang:用最遭也可以在O(nlgn) 09/22 16:48
推 DJWS:快速排序法 但是只有包含前1000個點的那一個半邊會遞迴下去 09/22 17:41
→ DJWS:average-case的時間複雜度也許是O(k*lgk + n) 09/22 17:43
→ DJWS:或者是選第i大的數字，選個1000次 時間複雜度O(k*n) 09/22 17:45
→ DJWS:或者是套用資料結構kd tree或range tree或octree等等等等等 09/22 17:47
→ DJWS:至於時間複雜度...請參考維基百科...謝謝 09/22 17:47
推 singlovesong:用隨便一種平衡樹都是klgk+n吧 ? 09/22 20:30
推 yoco315:作業 ＠＠？ 09/22 22:49
推 ledia:都找出第 i 小了, 再掃一次把比他小的篩出來就好 09/23 00:08
→ shaopin:DJWS大真是太強了 09/23 01:08
→ shaopin:FB interview question... 09/23 01:09
推 DJWS:ledia的方法最快 只有O(n) 09/23 10:13
→ DJWS:singlovesong, 如果用平衡樹直接處理應該是(n+k)*lgn 09/23 10:14
推 suhorng:quicksort只找前1000那邊遞迴下去, 應該也可以期望O(n)? 09/23 12:05
→ suhorng:其實就是四樓的方法 只不過四樓用的是穩定O(n)的方法 09/23 12:05
→ suhorng:quicksort只遞迴半邊下去好像只有"期望" O(n) 09/23 12:05
推 JingXD:應該是nlgk + n @@ 09/23 14:02
推 yoco315:的確 = =|| ledia 太驚人了... O(n) 09/23 15:05
→ yoco315:先用中位數那個 O(n) 的演算法找出第 1000 個 09/23 15:06
→ yoco315:然後再掃一次列出來就好.. O(n) -____- 天哪我沒想到.. 09/23 15:06
→ chunhsiang:題目並沒要求選出來的點集需要排序 O(klgk+n)可用O(n) 09/23 20:24
推 eieio:如果點數太多沒辦法一次放進 memory 的話，就做個 min-heap 09/24 09:12
→ eieio:然後裡面只存著「目前為止最近的 1000 點」 09/24 09:12
→ devilqxect:應該是max-heap? 09/24 09:18
推 eieio:Yes, should be max-heap. I was wrong 09/24 14:04
推 singlovesong:為什麼是max-heap? 雖然加個-號兩者基本上是一樣的 09/24 15:15
→ singlovesong:但min-heap 比較直覺吧 09/24 15:15
推 godgunman:用Bucket Sort來排序整數就好了（距離不要開根號 09/24 16:27
推 DJWS:用max-heap是要把比較大的數字delete掉，留下比較小的數字 09/24 22:06
推 eieio:因為 max-heap 可以 O(1) 找 heap 裡最大的 (目前第一千小) 09/26 04:06
→ eieio:有新的 element 比 第一千小 還小，就要換掉/更新 09/26 04:07
推 bigbite:如果點的坐標是integer, 可以用Hilbert curve轉換成1d 10/02 12:53