d*********i
发帖数: 104 | 1 Given 2D coordinates , find the k points which are closest to the origin.
Propose a data structure for storing the points and the method to get the k
points. Also point out the complexity of the code.
好像见讨论过，怎么做比较好呢 |
p*****2
发帖数: 21240 | 2
k
priority queue?
【在 d*********i 的大作中提到】
: Given 2D coordinates , find the k points which are closest to the origin.
: Propose a data structure for storing the points and the method to get the k
: points. Also point out the complexity of the code.
: 好像见讨论过，怎么做比较好呢
|
B***i
发帖数: 724 | |
D**********d
发帖数: 849 | |
d*********i
发帖数: 104 | 5
恩 我也觉得pq, max-heap 这个可行，不知道还有没有更优呢
【在 D**********d 的大作中提到】
: max-heap O(nlg(k))
|
f*****e
发帖数: 2992 | 6 quick-sort similar idea, find the kth element in n elements. All elements on
its right are suitable candidates. Not good for online large data.
【在 d*********i 的大作中提到】
:
: 恩 我也觉得pq, max-heap 这个可行，不知道还有没有更优呢
|
c********t
发帖数: 5706 | 7 感觉已经最优，除非要求O（1）空间，只能in place sort,时间复杂度就是O(nlogn)了
【在 d*********i 的大作中提到】
:
: 恩 我也觉得pq, max-heap 这个可行，不知道还有没有更优呢
|
l*******b
发帖数: 2586 | 8 heap本身就可以in place 实现吧。O(n)时间构造，O(k log n) 提取k个最小的
【在 c********t 的大作中提到】
: 感觉已经最优，除非要求O（1）空间，只能in place sort,时间复杂度就是O(nlogn)了
|
g*****e
发帖数: 282 | 9 面过一个类似的题，其他相同，但不是求离原点最近k个，而是对任意输入，求离这个
点最近的k个点，k是常数。
我给出的是BF，分支定界，但time complexity不变。any better idea?
【在 c********t 的大作中提到】
: 感觉已经最优，除非要求O（1）空间，只能in place sort,时间复杂度就是O(nlogn)了
|
c********t
发帖数: 5706 | 10 说到这里，我有很菜的java问题，heap,map,set, list,如果存的是object,应该只是存
储reference.对吧? 但是也要算作O(n)储存空间吧，怎么能算in place呢？
你可能与上面说的方法不同,解法是构造 k size的 max heap O(n log k);
【在 l*******b 的大作中提到】
: heap本身就可以in place 实现吧。O(n)时间构造，O(k log n) 提取k个最小的
|
|
|
c********t
发帖数: 5706 | 11 感觉是一样的，只是每个点先要算一下到给定点距离,比较距离
【在 g*****e 的大作中提到】
: 面过一个类似的题，其他相同，但不是求离原点最近k个，而是对任意输入，求离这个
: 点最近的k个点，k是常数。
: 我给出的是BF，分支定界，但time complexity不变。any better idea?
|
l*******b
发帖数: 2586 | 12 嗯，我想的是做一遍heap sort. 数据太大应该用辅助空间比较好。
【在 c********t 的大作中提到】
: 说到这里，我有很菜的java问题，heap,map,set, list,如果存的是object,应该只是存
: 储reference.对吧? 但是也要算作O(n)储存空间吧，怎么能算in place呢？
: 你可能与上面说的方法不同,解法是构造 k size的 max heap O(n log k);
|
c********s
发帖数: 817 | 13 > k size的 max heap
弱问：when building the heap, 如果新的element最终被放到 > k position时，就是
如何知道新的element不在
top k positions，if 只用k size heap？ 对k有特殊的要求吗 （power of 2－1）？
【在 c********t 的大作中提到】
: 说到这里，我有很菜的java问题，heap,map,set, list,如果存的是object,应该只是存
: 储reference.对吧? 但是也要算作O(n)储存空间吧，怎么能算in place呢？
: 你可能与上面说的方法不同,解法是构造 k size的 max heap O(n log k);
|
l*******b
发帖数: 2586 | 14 没要求吧，新的元素不会被放到 >k的位置呀，先和root比较，如果比root大，就直接
丢了。比root 小就把root 丢了，新的元素插到root然后sift down.
root存的是最大的元素，所以叫max heap吧。最后找到的却是所有n个元素里，k个最小
的。
【在 c********s 的大作中提到】
: > k size的 max heap
: 弱问：when building the heap, 如果新的element最终被放到 > k position时，就是
: 如何知道新的element不在
: top k positions，if 只用k size heap？ 对k有特殊的要求吗 （power of 2－1）？
|
c********s
发帖数: 817 | 15 懂了，谢谢！
【在 l*******b 的大作中提到】
: 没要求吧，新的元素不会被放到 >k的位置呀，先和root比较，如果比root大，就直接
: 丢了。比root 小就把root 丢了，新的元素插到root然后sift down.
: root存的是最大的元素，所以叫max heap吧。最后找到的却是所有n个元素里，k个最小
: 的。
|
g*****e
发帖数: 282 | 16 我总感觉可以怎么预处理一下，减少重复计算 =)
【在 c********t 的大作中提到】
: 感觉是一样的，只是每个点先要算一下到给定点距离,比较距离
|
