d******u 发帖数: 397 | 1 这题以前板上应该讨论过, 搜了一下没找到link
这题的变体就是那个找离地球最近的stars。。。
我能想到的就是build一个max heap,里面包含k个离原点最近的点
每读一个新的点,跟root比,比root小就加到heap里面,把root删掉,调整heap。
这个的时间复杂度是 O(nlgk), space是O(k)
请问还有别的方法吗? |
z*********8 发帖数: 2070 | 2 应该只有这个了
【在 d******u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这题以前板上应该讨论过, 搜了一下没找到link : 这题的变体就是那个找离地球最近的stars。。。 : 我能想到的就是build一个max heap,里面包含k个离原点最近的点 : 每读一个新的点,跟root比,比root小就加到heap里面,把root删掉,调整heap。 : 这个的时间复杂度是 O(nlgk), space是O(k) : 请问还有别的方法吗?
|
c*****r 发帖数: 108 | 3 基本上好像就这个思路,但是有个叫k-d tree的是解决general case的。但是这个k-d
tree比较偏门了。 还有就是在计算距离的时候 乘法会比较消耗时间,可以考虑做圆
的外接正方形的思路,缩小范围以后再提取k个点。
这个是我以前遇到过的问题,也不知道对不对,面试官是比较肯定的。 |
w****o 发帖数: 2260 | 4 “还有就是在计算距离的时候 乘法会比较消耗时间,可以考虑做圆
的外接正方形的思路,缩小范围以后再提取k个点。”
clouder,
能否在详细的讲讲你的方法?这些百万个3d的点,是如何存储的?如何组织的?是放在
一个数组里吗?
谢谢!
d
【在 c*****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 基本上好像就这个思路,但是有个叫k-d tree的是解决general case的。但是这个k-d : tree比较偏门了。 还有就是在计算距离的时候 乘法会比较消耗时间,可以考虑做圆 : 的外接正方形的思路,缩小范围以后再提取k个点。 : 这个是我以前遇到过的问题,也不知道对不对,面试官是比较肯定的。
|
z********c 发帖数: 72 | 5 那快速选择算法呢?
算出距离以后,按照快排的思想选取pivot划分成左集合和右集合,如果左集合大于k,
那么只用对左集合选取前k个就行,否则左集合都属于k个点,然后对右集合选取距离最
小的k - size(左集合)
【在 d******u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这题以前板上应该讨论过, 搜了一下没找到link : 这题的变体就是那个找离地球最近的stars。。。 : 我能想到的就是build一个max heap,里面包含k个离原点最近的点 : 每读一个新的点,跟root比,比root小就加到heap里面,把root删掉,调整heap。 : 这个的时间复杂度是 O(nlgk), space是O(k) : 请问还有别的方法吗?
|
d******u 发帖数: 397 | 6 这个优化的idea不错,但是,如果以圆的外界正方形为判断标准的话,返回k个点就不
够了,因为会有一些点落在正方形里面,圆形外面
这时候可以按照圆和正方形的面积比取多一些点,但还是不能保证,一次能找到k个点
d
【在 c*****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 基本上好像就这个思路,但是有个叫k-d tree的是解决general case的。但是这个k-d : tree比较偏门了。 还有就是在计算距离的时候 乘法会比较消耗时间,可以考虑做圆 : 的外接正方形的思路,缩小范围以后再提取k个点。 : 这个是我以前遇到过的问题,也不知道对不对,面试官是比较肯定的。
|
d******u 发帖数: 397 | 7 这个方法不错,时间复杂度是O(n),但空间呢。。。如果所有数不能同时load进内存的话
【在 z********c 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 那快速选择算法呢? : 算出距离以后,按照快排的思想选取pivot划分成左集合和右集合,如果左集合大于k, : 那么只用对左集合选取前k个就行,否则左集合都属于k个点,然后对右集合选取距离最 : 小的k - size(左集合)
|
c*****r 发帖数: 108 | 8 百万个点的数据结构,我当时遇到的时候被告知不用担心。就当作是streaming进来的
一个个点的坐标。或者说是一个个读取object。
另外,我遇到的二维的情况,所以可以认为接收到的object是 ( x, y). 然后距离计
算距离的时候就需要(x^2 + y^2).面试官说是否可以再快一点,这么多点计算乘法很
慢。 然后又说假设k很小。
我就说了用 2(|x| + |Y|)作为判断距离大小的标准,这样就只需要做位的左移操作和
绝对值操作了。有一定概率会发生错误但是既然k很小,又有百万个点。这个概率是很
小的。这样下来我们找到所有在这个 2(|x| + |Y|)以内的点以后,如果大于k个, 再
通过(x^2 + y^2)求最近的点。 大概就这个思路。当时面试官好像是肯定了这个想法
的。
不过如果你的面试官没有说可以忽略一定的概率,这个方法可能不行哦。
【在 w****o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : “还有就是在计算距离的时候 乘法会比较消耗时间,可以考虑做圆 : 的外接正方形的思路,缩小范围以后再提取k个点。” : clouder, : 能否在详细的讲讲你的方法?这些百万个3d的点,是如何存储的?如何组织的?是放在 : 一个数组里吗? : 谢谢! : : d
|
s*********d 发帖数: 2406 | 9 K-d tree 和 NNS 基本上能解决
反正俺是被amazon问倒了。 |
c*****r 发帖数: 108 | 10 小弟也是amazon 问到的
【在 s*********d 的大作中提到】![](/moin_static193/solenoid/img/up.png) : K-d tree 和 NNS 基本上能解决 : 反正俺是被amazon问倒了。
|
|
|
w****o 发帖数: 2260 | 11 什么是 k-d tree?
是不是如果是一维的点的话,就不用这些优化了,直接用首贴的LZ的max_heap方法就行
了?
【在 s*********d 的大作中提到】![](/moin_static193/solenoid/img/up.png) : K-d tree 和 NNS 基本上能解决 : 反正俺是被amazon问倒了。
|
w****o 发帖数: 2260 | 12 这个快速选择的方法的复杂度怎么是 O(n)呢?
的话
【在 d******u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个方法不错,时间复杂度是O(n),但空间呢。。。如果所有数不能同时load进内存的话
|
d******u 发帖数: 397 | 13 这题以前板上应该讨论过, 搜了一下没找到link
这题的变体就是那个找离地球最近的stars。。。
我能想到的就是build一个max heap,里面包含k个离原点最近的点
每读一个新的点,跟root比,比root小就加到heap里面,把root删掉,调整heap。
这个的时间复杂度是 O(nlgk), space是O(k)
请问还有别的方法吗? |
z*********8 发帖数: 2070 | 14 应该只有这个了
【在 d******u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这题以前板上应该讨论过, 搜了一下没找到link : 这题的变体就是那个找离地球最近的stars。。。 : 我能想到的就是build一个max heap,里面包含k个离原点最近的点 : 每读一个新的点,跟root比,比root小就加到heap里面,把root删掉,调整heap。 : 这个的时间复杂度是 O(nlgk), space是O(k) : 请问还有别的方法吗?
|
c*****r 发帖数: 108 | 15 基本上好像就这个思路,但是有个叫k-d tree的是解决general case的。但是这个k-d
tree比较偏门了。 还有就是在计算距离的时候 乘法会比较消耗时间,可以考虑做圆
的外接正方形的思路,缩小范围以后再提取k个点。
这个是我以前遇到过的问题,也不知道对不对,面试官是比较肯定的。 |
w****o 发帖数: 2260 | 16 “还有就是在计算距离的时候 乘法会比较消耗时间,可以考虑做圆
的外接正方形的思路,缩小范围以后再提取k个点。”
clouder,
能否在详细的讲讲你的方法?这些百万个3d的点,是如何存储的?如何组织的?是放在
一个数组里吗?
谢谢!
d
【在 c*****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 基本上好像就这个思路,但是有个叫k-d tree的是解决general case的。但是这个k-d : tree比较偏门了。 还有就是在计算距离的时候 乘法会比较消耗时间,可以考虑做圆 : 的外接正方形的思路,缩小范围以后再提取k个点。 : 这个是我以前遇到过的问题,也不知道对不对,面试官是比较肯定的。
|
z********c 发帖数: 72 | 17 那快速选择算法呢?
算出距离以后,按照快排的思想选取pivot划分成左集合和右集合,如果左集合大于k,
那么只用对左集合选取前k个就行,否则左集合都属于k个点,然后对右集合选取距离最
小的k - size(左集合)
【在 d******u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这题以前板上应该讨论过, 搜了一下没找到link : 这题的变体就是那个找离地球最近的stars。。。 : 我能想到的就是build一个max heap,里面包含k个离原点最近的点 : 每读一个新的点,跟root比,比root小就加到heap里面,把root删掉,调整heap。 : 这个的时间复杂度是 O(nlgk), space是O(k) : 请问还有别的方法吗?
|
d******u 发帖数: 397 | 18 这个优化的idea不错,但是,如果以圆的外界正方形为判断标准的话,返回k个点就不
够了,因为会有一些点落在正方形里面,圆形外面
这时候可以按照圆和正方形的面积比取多一些点,但还是不能保证,一次能找到k个点
d
【在 c*****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 基本上好像就这个思路,但是有个叫k-d tree的是解决general case的。但是这个k-d : tree比较偏门了。 还有就是在计算距离的时候 乘法会比较消耗时间,可以考虑做圆 : 的外接正方形的思路,缩小范围以后再提取k个点。 : 这个是我以前遇到过的问题,也不知道对不对,面试官是比较肯定的。
|
d******u 发帖数: 397 | 19 这个方法不错,时间复杂度是O(n),但空间呢。。。如果所有数不能同时load进内存的话
【在 z********c 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 那快速选择算法呢? : 算出距离以后,按照快排的思想选取pivot划分成左集合和右集合,如果左集合大于k, : 那么只用对左集合选取前k个就行,否则左集合都属于k个点,然后对右集合选取距离最 : 小的k - size(左集合)
|
c*****r 发帖数: 108 | 20 百万个点的数据结构,我当时遇到的时候被告知不用担心。就当作是streaming进来的
一个个点的坐标。或者说是一个个读取object。
另外,我遇到的二维的情况,所以可以认为接收到的object是 ( x, y). 然后距离计
算距离的时候就需要(x^2 + y^2).面试官说是否可以再快一点,这么多点计算乘法很
慢。 然后又说假设k很小。
我就说了用 2(|x| + |Y|)作为判断距离大小的标准,这样就只需要做位的左移操作和
绝对值操作了。有一定概率会发生错误但是既然k很小,又有百万个点。这个概率是很
小的。这样下来我们找到所有在这个 2(|x| + |Y|)以内的点以后,如果大于k个, 再
通过(x^2 + y^2)求最近的点。 大概就这个思路。当时面试官好像是肯定了这个想法
的。
不过如果你的面试官没有说可以忽略一定的概率,这个方法可能不行哦。
【在 w****o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : “还有就是在计算距离的时候 乘法会比较消耗时间,可以考虑做圆 : 的外接正方形的思路,缩小范围以后再提取k个点。” : clouder, : 能否在详细的讲讲你的方法?这些百万个3d的点,是如何存储的?如何组织的?是放在 : 一个数组里吗? : 谢谢! : : d
|
|
|
s*********d 发帖数: 2406 | 21 K-d tree 和 NNS 基本上能解决
反正俺是被amazon问倒了。 |
c*****r 发帖数: 108 | 22 小弟也是amazon 问到的
【在 s*********d 的大作中提到】![](/moin_static193/solenoid/img/up.png) : K-d tree 和 NNS 基本上能解决 : 反正俺是被amazon问倒了。
|
w****o 发帖数: 2260 | 23 什么是 k-d tree?
是不是如果是一维的点的话,就不用这些优化了,直接用首贴的LZ的max_heap方法就行
了?
【在 s*********d 的大作中提到】![](/moin_static193/solenoid/img/up.png) : K-d tree 和 NNS 基本上能解决 : 反正俺是被amazon问倒了。
|
w****o 发帖数: 2260 | 24 这个快速选择的方法的复杂度怎么是 O(n)呢?
的话
【在 d******u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个方法不错,时间复杂度是O(n),但空间呢。。。如果所有数不能同时load进内存的话
|
b******7 发帖数: 92 | 25 因为递归式平均情况是T(n) = T(n/2) + O(n),所以是O(n)
参见算法导论第9章select k问题,随机划分平均性能O(n), 精细划分最坏情况O(n)
【在 w****o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个快速选择的方法的复杂度怎么是 O(n)呢? : : 的话
|
b******7 发帖数: 92 | 26 1、建k最大堆时同时计算该堆所有点所在的外接矩形,{max(x),max(y)}
2、后续n-k点每次通过比较是否落入矩形,若落入矩形内才计算距离并与堆顶元素比较
,若入堆,根据改点维护外接矩形
应该没有什么概率问题
【在 c*****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 百万个点的数据结构,我当时遇到的时候被告知不用担心。就当作是streaming进来的 : 一个个点的坐标。或者说是一个个读取object。 : 另外,我遇到的二维的情况,所以可以认为接收到的object是 ( x, y). 然后距离计 : 算距离的时候就需要(x^2 + y^2).面试官说是否可以再快一点,这么多点计算乘法很 : 慢。 然后又说假设k很小。 : 我就说了用 2(|x| + |Y|)作为判断距离大小的标准,这样就只需要做位的左移操作和 : 绝对值操作了。有一定概率会发生错误但是既然k很小,又有百万个点。这个概率是很 : 小的。这样下来我们找到所有在这个 2(|x| + |Y|)以内的点以后,如果大于k个, 再 : 通过(x^2 + y^2)求最近的点。 大概就这个思路。当时面试官好像是肯定了这个想法 : 的。
|
d**********x 发帖数: 4083 | 27 上次讨论过这个kd-tree
这东西适合多次查询
只算一次的话就quick selection
d
【在 c*****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 基本上好像就这个思路,但是有个叫k-d tree的是解决general case的。但是这个k-d : tree比较偏门了。 还有就是在计算距离的时候 乘法会比较消耗时间,可以考虑做圆 : 的外接正方形的思路,缩小范围以后再提取k个点。 : 这个是我以前遇到过的问题,也不知道对不对,面试官是比较肯定的。
|
j*****n 发帖数: 1545 | 28 你要知道 k-d tree 或者 ball-tree, metric-tree 就可以提一提。 不会让你实现的。 |
b******7 发帖数: 92 | 29 因为递归式平均情况是T(n) = T(n/2) + O(n),所以是O(n)
参见算法导论第9章select k问题,随机划分平均性能O(n), 精细划分最坏情况O(n)
【在 w****o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个快速选择的方法的复杂度怎么是 O(n)呢? : : 的话
|
b******7 发帖数: 92 | 30 1、建k最大堆时同时计算该堆所有点所在的外接矩形,{max(x),max(y)}
2、后续n-k点每次通过比较是否落入矩形,若落入矩形内才计算距离并与堆顶元素比较
,若入堆,根据改点维护外接矩形
应该没有什么概率问题
【在 c*****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 百万个点的数据结构,我当时遇到的时候被告知不用担心。就当作是streaming进来的 : 一个个点的坐标。或者说是一个个读取object。 : 另外,我遇到的二维的情况,所以可以认为接收到的object是 ( x, y). 然后距离计 : 算距离的时候就需要(x^2 + y^2).面试官说是否可以再快一点,这么多点计算乘法很 : 慢。 然后又说假设k很小。 : 我就说了用 2(|x| + |Y|)作为判断距离大小的标准,这样就只需要做位的左移操作和 : 绝对值操作了。有一定概率会发生错误但是既然k很小,又有百万个点。这个概率是很 : 小的。这样下来我们找到所有在这个 2(|x| + |Y|)以内的点以后,如果大于k个, 再 : 通过(x^2 + y^2)求最近的点。 大概就这个思路。当时面试官好像是肯定了这个想法 : 的。
|
|
|
d**********x 发帖数: 4083 | 31 上次讨论过这个kd-tree
这东西适合多次查询
只算一次的话就quick selection
d
【在 c*****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 基本上好像就这个思路,但是有个叫k-d tree的是解决general case的。但是这个k-d : tree比较偏门了。 还有就是在计算距离的时候 乘法会比较消耗时间,可以考虑做圆 : 的外接正方形的思路,缩小范围以后再提取k个点。 : 这个是我以前遇到过的问题,也不知道对不对,面试官是比较肯定的。
|
j*****n 发帖数: 1545 | 32 你要知道 k-d tree 或者 ball-tree, metric-tree 就可以提一提。 不会让你实现的。 |
s*****n 发帖数: 5488 | 33 开始随机取k点,加入heap.建立bounding box. MBB(k)
性质:MBB(k) monotonically shrinks.
filering: if p(k) is not in MBB(k), discard.
这个计算会越来越快。因为MBB越来越小。
什么组,要考spatial index方面的知识?
【在 c*****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 百万个点的数据结构,我当时遇到的时候被告知不用担心。就当作是streaming进来的 : 一个个点的坐标。或者说是一个个读取object。 : 另外,我遇到的二维的情况,所以可以认为接收到的object是 ( x, y). 然后距离计 : 算距离的时候就需要(x^2 + y^2).面试官说是否可以再快一点,这么多点计算乘法很 : 慢。 然后又说假设k很小。 : 我就说了用 2(|x| + |Y|)作为判断距离大小的标准,这样就只需要做位的左移操作和 : 绝对值操作了。有一定概率会发生错误但是既然k很小,又有百万个点。这个概率是很 : 小的。这样下来我们找到所有在这个 2(|x| + |Y|)以内的点以后,如果大于k个, 再 : 通过(x^2 + y^2)求最近的点。 大概就这个思路。当时面试官好像是肯定了这个想法 : 的。
|
a*******3 发帖数: 27 | 34 如果k很小,常数级别,或者k很大,跟n的差值是常数级别,都可以用最大,最小堆来
做吧
如果k跟n较接近,如n/2,感觉还是用partition的方法比较好
本题不适合多次查询,或者多次查询k近邻,所以感觉kd-tree之类的index不太合适,
复杂度偏高。 |
d*********g 发帖数: 154 | 35
为什么2(|x| + |Y|)而不是(|x| + |Y|)?应该没区别吧?
【在 c*****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 百万个点的数据结构,我当时遇到的时候被告知不用担心。就当作是streaming进来的 : 一个个点的坐标。或者说是一个个读取object。 : 另外,我遇到的二维的情况,所以可以认为接收到的object是 ( x, y). 然后距离计 : 算距离的时候就需要(x^2 + y^2).面试官说是否可以再快一点,这么多点计算乘法很 : 慢。 然后又说假设k很小。 : 我就说了用 2(|x| + |Y|)作为判断距离大小的标准,这样就只需要做位的左移操作和 : 绝对值操作了。有一定概率会发生错误但是既然k很小,又有百万个点。这个概率是很 : 小的。这样下来我们找到所有在这个 2(|x| + |Y|)以内的点以后,如果大于k个, 再 : 通过(x^2 + y^2)求最近的点。 大概就这个思路。当时面试官好像是肯定了这个想法 : 的。
|
a*******3 发帖数: 27 | 36 streaming方式的话用heap吧,把在heap中的的点的最小x,y,最大x,y都保存,这四个
值可以构成一个矩形,在这个矩形之外的点直接filter,在矩形里面的才计算然后跟
heap top的元素比较 |
a********m 发帖数: 15480 | |