作者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