PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[問題] 一個面試問題

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