C***y 发帖数: 2546 | 1 好像不少人被面过
这题最优的解应该是什么?
我能想到的就是算出距离,然后用最大堆了 |
f*******4 发帖数: 1401 | |
g***s 发帖数: 3811 | 3 这算法是O(100n)=O(n),还不满足?算个所有距离也需要O(n)啊
【在 C***y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 好像不少人被面过 : 这题最优的解应该是什么? : 我能想到的就是算出距离,然后用最大堆了
|
Z**********4 发帖数: 528 | |
C***y 发帖数: 2546 | 5 max heap
【在 Z**********4 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 弱问下 最大堆是什么
|
Z**********4 发帖数: 528 | 6 那最大堆的建堆时间不用计算到复杂度里面么?如果需要就不是O(n)了吧
【在 C***y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : max heap
|
C***y 发帖数: 2546 | 7 O(nlg100) = O(n)
【在 Z**********4 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 那最大堆的建堆时间不用计算到复杂度里面么?如果需要就不是O(n)了吧
|
g***s 发帖数: 3811 | 8 最大堆的建堆时间O(n)
【在 Z**********4 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 那最大堆的建堆时间不用计算到复杂度里面么?如果需要就不是O(n)了吧
|
g***s 发帖数: 3811 | 9 严格的话,应该是
O(n)+O(100* lg n)=O(n)
在 Chevy (Chevy) 的大作中提到: 】 |
C***y 发帖数: 2546 | 10 建一个size=100的堆
【在 g***s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 严格的话,应该是 : O(n)+O(100* lg n)=O(n) : 在 Chevy (Chevy) 的大作中提到: 】
|
|
|
g***s 发帖数: 3811 | 11 不对吧。必须建立size=n的堆。然后取最大,调整,做100次
【在 C***y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 建一个size=100的堆
|
P********l 发帖数: 452 | 12 If the heap size is m, heapify = O(m log(m) ).
【在 g***s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 最大堆的建堆时间O(n)
|
g***s 发帖数: 3811 | 13 no. it is O(m).
【在 P********l 的大作中提到】![](/moin_static193/solenoid/img/up.png) : If the heap size is m, heapify = O(m log(m) ).
|
c**********6 发帖数: 105 | 14 1. O(n): compute all the distances to the original point.
2. O(n): use partition algorithm the get the 100th smallest distance.
3. O(n): get all those points whose distance to the original point is
smaller than 100th smallest dist.
O(n)+O(n)+O(n)=O(n) |
r*****h 发帖数: 505 | 15 还是heap好,O(n)和O(n)也有区别的
【在 c**********6 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 1. O(n): compute all the distances to the original point. : 2. O(n): use partition algorithm the get the 100th smallest distance. : 3. O(n): get all those points whose distance to the original point is : smaller than 100th smallest dist. : O(n)+O(n)+O(n)=O(n)
|
g***s 发帖数: 3811 | 16 不错,另外一个解法。
【在 c**********6 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 1. O(n): compute all the distances to the original point. : 2. O(n): use partition algorithm the get the 100th smallest distance. : 3. O(n): get all those points whose distance to the original point is : smaller than 100th smallest dist. : O(n)+O(n)+O(n)=O(n)
|