d***t
发帖数: 57 | 1 1. 找数组中的duplicate
2. 一个文件里有billions of unsorted星坐标，返回M个离地心最近的stars |
c******a
发帖数: 789 | |
a*****u
发帖数: 1712 | 3 第二题怎么做
★ 发自iPhone App: ChineseWeb 7.8
【在 d***t 的大作中提到】
: 1. 找数组中的duplicate
: 2. 一个文件里有billions of unsorted星坐标，返回M个离地心最近的stars
|
r**h
发帖数: 1288 | 4 不考虑大数据的话直接quick selection
否则可以用heap
【在 a*****u 的大作中提到】
: 第二题怎么做
:
: ★ 发自iPhone App: ChineseWeb 7.8
|
c********p
发帖数: 1969 | 5 你咋这么聪明呢！
【在 r**h 的大作中提到】
: 不考虑大数据的话直接quick selection
: 否则可以用heap
|
c******a
发帖数: 789 | 6 大数据用heap不行，听说会被直接拖出去的。
有partition之类的方法预处理，具体我不记得了。
【在 r**h 的大作中提到】
: 不考虑大数据的话直接quick selection
: 否则可以用heap
|
p*****3
发帖数: 488 | 7
分批merge吧
【在 c******a 的大作中提到】
: 大数据用heap不行，听说会被直接拖出去的。
: 有partition之类的方法预处理，具体我不记得了。
|
c******a
发帖数: 789 | 8 这个当然好。
预处理可以很customized，尤其是对于坐标，实在是忘记了。。。。大家没事看看这个
https://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm
【在 p*****3 的大作中提到】
:
: 分批merge吧
|
a*****u
发帖数: 1712 | 9 奥，刚刚想复杂了，谢谢
【在 r**h 的大作中提到】
: 不考虑大数据的话直接quick selection
: 否则可以用heap
|
u*****o
发帖数: 1224 | 10 HEAP的TIME是nlogk吧。虽然SPACE只用了O(k)
我觉得用这个QUICK SELECT的升级版
http://stackoverflow.com/questions/9202315/algorithm-to-find-10
time O(n)， space O(k) |
x*****0
发帖数: 452 | |
s***5
发帖数: 2136 | 12 那个方法真的好吗？不就是CLRS上的求k-statistics吗？记住输入如果是坐标值，你得
先把所有distance算出来存到另一个数组，再不停swap，time虽然是O(n)，但是那个
constant不小，空间应该是O(n+k)。
用heap只需要一个元素数目为k的maxheap，算出一个distance值就往heap里插再
heapify。n多大都不成问题。
【在 u*****o 的大作中提到】
: HEAP的TIME是nlogk吧。虽然SPACE只用了O(k)
: 我觉得用这个QUICK SELECT的升级版
: http://stackoverflow.com/questions/9202315/algorithm-to-find-10
: time O(n)， space O(k)
|
h****p
发帖数: 87 | |
