感觉应该建立个max heap, 每次比较某点距离dist和top of max heap, if dist < max_heap.top, then pop max_heap, push dist; else ignore, do nothing; 最后得到的就是k smallest distances啦
【在 l*******A 的大作中提到】 : 第三题建个最小堆 : 然后remove top element k times?
【在 k*******t 的大作中提到】 : 感觉应该建立个max heap, 每次比较某点距离dist和top of max heap, : if dist < max_heap.top, then pop max_heap, push dist; : else ignore, do nothing; : 最后得到的就是k smallest distances啦
Problem 3: Using Min heap: 1. Create a pair list(key:distance;value:coordinate). O(n) 2. Build a Min heap based on key. O(n) 3. Get values of the first Ks of key from Min heap. O(K) Time complexity: O(n)
【在 k*******t 的大作中提到】 : 感觉应该建立个max heap, 每次比较某点距离dist和top of max heap, : if dist < max_heap.top, then pop max_heap, push dist; : else ignore, do nothing; : 最后得到的就是k smallest distances啦
【在 f*******b 的大作中提到】 : Problem 3: : Using Min heap: : 1. Create a pair list(key:distance;value:coordinate). O(n) : 2. Build a Min heap based on key. O(n) : 3. Get values of the first Ks of key from Min heap. O(K) : Time complexity: O(n)