Amazon OA1 Coding 新题

给一个CPoint数组，求离原点最近的k个点。
class CPoint{

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

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

。 test cases 都过了。

loveonts 发表于 2015-12-6 12:34
C++一个map就行吧 hash[dist] = point. 然后 C++ STL里的map本来已经排好序 一位一位读就可以了吧？
实在 ...

可行，反正别用O(nlogn)的方法

yjtwm 发表于 2015-12-25 03:39
楼主，这题不是quick select吗？
直接套leetcode： Kth Largest Element in an Array
可以实现avg O（n） ...

前K个和第K个还是不一样吧？

bihuang0910 发表于 2015-12-26 04:24
前K个和第K个还是不一样吧？

不错，但你得到第k个以后再遍历一遍把小于k的拿出来也还是O（n），所以整体还是O（n）

请问排序用的是heap还是直接Arrays.sort()或者其他的呢

这个题原来是OA2里面的吧？

C++一个map就行吧 hash[dist] = point. 然后 C++ STL里的map本来已经排好序 一位一位读就可以了吧？
实在不行 hashmap 加 BST 或heap 也行

eamon_felix4213 发表于 2015-12-1 09:50
请问排序用的是heap还是直接Arrays.sort()或者其他的呢

直接sort排的，不要学我，我后来onsite了

各位我后来onsite去了，所以强烈建议好好写，写个O(n)的解法

jiujiu0818 发表于 2015-12-6 23:28
可行，反正别用O(nlogn)的方法

onsite加油吧 我还在默默地等OA1 已经过了一个月了 话说楼主啥时候投的啊？

loveonts 发表于 2015-12-7 08:33
onsite加油吧 我还在默默地等OA1 已经过了一个月了 话说楼主啥时候投的啊？

九月中。。。

楼主，这题不是quick select吗？
直接套leetcode： Kth Largest Element in an Array
可以实现avg O（n） time