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 的大作中提到】
: 这题以前板上应该讨论过， 搜了一下没找到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 的大作中提到】
: 基本上好像就这个思路，但是有个叫k-d tree的是解决general case的。但是这个k-d
: tree比较偏门了。 还有就是在计算距离的时候 乘法会比较消耗时间，可以考虑做圆
: 的外接正方形的思路，缩小范围以后再提取k个点。
: 这个是我以前遇到过的问题，也不知道对不对，面试官是比较肯定的。
|
z********c
发帖数: 72 | 5 那快速选择算法呢？
算出距离以后，按照快排的思想选取pivot划分成左集合和右集合，如果左集合大于k，
那么只用对左集合选取前k个就行，否则左集合都属于k个点，然后对右集合选取距离最
小的k - size(左集合)
【在 d******u 的大作中提到】
: 这题以前板上应该讨论过， 搜了一下没找到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 的大作中提到】
: 基本上好像就这个思路，但是有个叫k-d tree的是解决general case的。但是这个k-d
: tree比较偏门了。 还有就是在计算距离的时候 乘法会比较消耗时间，可以考虑做圆
: 的外接正方形的思路，缩小范围以后再提取k个点。
: 这个是我以前遇到过的问题，也不知道对不对，面试官是比较肯定的。
|
d******u
发帖数: 397 | 7 这个方法不错，时间复杂度是O(n)，但空间呢。。。如果所有数不能同时load进内存的话
【在 z********c 的大作中提到】
: 那快速选择算法呢？
: 算出距离以后，按照快排的思想选取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 的大作中提到】
: “还有就是在计算距离的时候 乘法会比较消耗时间，可以考虑做圆
: 的外接正方形的思路，缩小范围以后再提取k个点。”
: clouder,
: 能否在详细的讲讲你的方法？这些百万个3d的点，是如何存储的？如何组织的？是放在
: 一个数组里吗？
: 谢谢！
:
: d
|
s*********d
发帖数: 2406 | 9 K-d tree 和 NNS 基本上能解决
反正俺是被amazon问倒了。 |
c*****r
发帖数: 108 | 10 小弟也是amazon 问到的
【在 s*********d 的大作中提到】
: K-d tree 和 NNS 基本上能解决
: 反正俺是被amazon问倒了。
|
|
|
w****o
发帖数: 2260 | 11 什么是 k-d tree?
是不是如果是一维的点的话，就不用这些优化了，直接用首贴的LZ的max_heap方法就行
了？
【在 s*********d 的大作中提到】
: K-d tree 和 NNS 基本上能解决
: 反正俺是被amazon问倒了。
|
w****o
发帖数: 2260 | 12 这个快速选择的方法的复杂度怎么是 O(n)呢？
的话
【在 d******u 的大作中提到】
: 这个方法不错，时间复杂度是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 的大作中提到】
: 这题以前板上应该讨论过， 搜了一下没找到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 的大作中提到】
: 基本上好像就这个思路，但是有个叫k-d tree的是解决general case的。但是这个k-d
: tree比较偏门了。 还有就是在计算距离的时候 乘法会比较消耗时间，可以考虑做圆
: 的外接正方形的思路，缩小范围以后再提取k个点。
: 这个是我以前遇到过的问题，也不知道对不对，面试官是比较肯定的。
|
z********c
发帖数: 72 | 17 那快速选择算法呢？
算出距离以后，按照快排的思想选取pivot划分成左集合和右集合，如果左集合大于k，
那么只用对左集合选取前k个就行，否则左集合都属于k个点，然后对右集合选取距离最
小的k - size(左集合)
【在 d******u 的大作中提到】
: 这题以前板上应该讨论过， 搜了一下没找到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 的大作中提到】
: 基本上好像就这个思路，但是有个叫k-d tree的是解决general case的。但是这个k-d
: tree比较偏门了。 还有就是在计算距离的时候 乘法会比较消耗时间，可以考虑做圆
: 的外接正方形的思路，缩小范围以后再提取k个点。
: 这个是我以前遇到过的问题，也不知道对不对，面试官是比较肯定的。
|
d******u
发帖数: 397 | 19 这个方法不错，时间复杂度是O(n)，但空间呢。。。如果所有数不能同时load进内存的话
【在 z********c 的大作中提到】
: 那快速选择算法呢？
: 算出距离以后，按照快排的思想选取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 的大作中提到】
: “还有就是在计算距离的时候 乘法会比较消耗时间，可以考虑做圆
: 的外接正方形的思路，缩小范围以后再提取k个点。”
: clouder,
: 能否在详细的讲讲你的方法？这些百万个3d的点，是如何存储的？如何组织的？是放在
: 一个数组里吗？
: 谢谢！
:
: d
|
|
|
s*********d
发帖数: 2406 | 21 K-d tree 和 NNS 基本上能解决
反正俺是被amazon问倒了。 |
c*****r
发帖数: 108 | 22 小弟也是amazon 问到的
【在 s*********d 的大作中提到】
: K-d tree 和 NNS 基本上能解决
: 反正俺是被amazon问倒了。
|
w****o
发帖数: 2260 | 23 什么是 k-d tree?
是不是如果是一维的点的话，就不用这些优化了，直接用首贴的LZ的max_heap方法就行
了？
【在 s*********d 的大作中提到】
: K-d tree 和 NNS 基本上能解决
: 反正俺是被amazon问倒了。
|
w****o
发帖数: 2260 | 24 这个快速选择的方法的复杂度怎么是 O(n)呢？
的话
【在 d******u 的大作中提到】
: 这个方法不错，时间复杂度是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 的大作中提到】
: 这个快速选择的方法的复杂度怎么是 O(n)呢？
:
: 的话
|
b******7
发帖数: 92 | 26 1、建k最大堆时同时计算该堆所有点所在的外接矩形，{max(x)，max(y)}
2、后续n-k点每次通过比较是否落入矩形，若落入矩形内才计算距离并与堆顶元素比较
，若入堆，根据改点维护外接矩形
应该没有什么概率问题
【在 c*****r 的大作中提到】
: 百万个点的数据结构，我当时遇到的时候被告知不用担心。就当作是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 的大作中提到】
: 基本上好像就这个思路，但是有个叫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 的大作中提到】
: 这个快速选择的方法的复杂度怎么是 O(n)呢？
:
: 的话
|
b******7
发帖数: 92 | 30 1、建k最大堆时同时计算该堆所有点所在的外接矩形，{max(x)，max(y)}
2、后续n-k点每次通过比较是否落入矩形，若落入矩形内才计算距离并与堆顶元素比较
，若入堆，根据改点维护外接矩形
应该没有什么概率问题
【在 c*****r 的大作中提到】
: 百万个点的数据结构，我当时遇到的时候被告知不用担心。就当作是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 的大作中提到】
: 基本上好像就这个思路，但是有个叫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 的大作中提到】
: 百万个点的数据结构，我当时遇到的时候被告知不用担心。就当作是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 的大作中提到】
: 百万个点的数据结构，我当时遇到的时候被告知不用担心。就当作是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 | |
