F脸家intern电面

可以用一个大小为k的sliding window边扫边存当前k个离原点最近的点吧，这样如果sliding window里的元素也用最大堆的话复杂度可以到O(nlogk)，内存也只用了O(k)，每次碰到比当前最大堆顶元素小的值，就pop掉然后push进新的值。因为有很多重复元素所以不能用库函数只能自己实现可重复元素的最大堆了

pwwpche 发表于 2016-11-15 12:48
可以用一个大小为k的sliding window边扫边存当前k个离原点最近的点吧，这样如果sliding window里的元素也用 ...

这个跟用堆有什么不一样么？

qiweiren 发表于 2016-11-15 15:15
这个跟用堆有什么不一样么？

可以看看leetcode 321,不需要排序，只扫一遍就能记录当前数组里面最小的k个数了

pwwpche 发表于 2016-11-15 15:51
可以看看leetcode 321,不需要排序，只扫一遍就能记录当前数组里面最小的k个数了

噢！懂了 大小顶堆问题 完全忘了 啊 好气啊

QuickSelect , k*O(n) time complexity

暂时想到两个，第一个可以quickselect 第K大，然后o(n)遍历一遍选出比这个点更近的所有点。第二个就是k窗口+最大堆。如果k值较大可以考虑第一个方法，k值小可以使用第二个

std::nth_element(first, nth, last),

补充内容 (2016-11-15 23:23):
complexity: build an array of square of distances to 0: O(n);  nth_element: O(n); in total: O(n)

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies