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