C***y
发帖数: 2546 | 1 好像不少人被面过
这题最优的解应该是什么？
我能想到的就是算出距离，然后用最大堆了 |
f*******4
发帖数: 1401 | |
g***s
发帖数: 3811 | 3 这算法是O(100n)=O(n)，还不满足？算个所有距离也需要O(n)啊
【在 C***y 的大作中提到】
: 好像不少人被面过
: 这题最优的解应该是什么？
: 我能想到的就是算出距离，然后用最大堆了
|
Z**********4
发帖数: 528 | |
C***y
发帖数: 2546 | 5 max heap
【在 Z**********4 的大作中提到】
: 弱问下 最大堆是什么
|
Z**********4
发帖数: 528 | 6 那最大堆的建堆时间不用计算到复杂度里面么？如果需要就不是O（n）了吧
【在 C***y 的大作中提到】
: max heap
|
C***y
发帖数: 2546 | 7 O(nlg100) = O(n)
【在 Z**********4 的大作中提到】
: 那最大堆的建堆时间不用计算到复杂度里面么？如果需要就不是O（n）了吧
|
g***s
发帖数: 3811 | 8 最大堆的建堆时间O(n)
【在 Z**********4 的大作中提到】
: 那最大堆的建堆时间不用计算到复杂度里面么？如果需要就不是O（n）了吧
|
g***s
发帖数: 3811 | 9 严格的话，应该是
O(n)+O(100* lg n)=O(n)
在 Chevy (Chevy) 的大作中提到: 】 |
C***y
发帖数: 2546 | 10 建一个size=100的堆
【在 g***s 的大作中提到】
: 严格的话，应该是
: O(n)+O(100* lg n)=O(n)
: 在 Chevy (Chevy) 的大作中提到: 】
|
|
|
g***s
发帖数: 3811 | 11 不对吧。必须建立size=n的堆。然后取最大，调整，做100次
【在 C***y 的大作中提到】
: 建一个size=100的堆
|
P********l
发帖数: 452 | 12 If the heap size is m, heapify = O(m log(m) ).
【在 g***s 的大作中提到】
: 最大堆的建堆时间O(n)
|
g***s
发帖数: 3811 | 13 no. it is O(m).
【在 P********l 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 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)
|
