google intern

感觉可以这样做，既然不能改动array：
如果k=1直接返回堆顶；
k=2返回max(堆顶的左右儿子)；
k=3返回max(max(堆顶的左右儿子)的左右儿子，min(堆顶的左右儿子的左右儿子))
这里面每次处理的都是堆，用下标表示。
每次都安顺序找出第k大的堆然后返回其堆顶即可。

PriorityQueue 然后弄个comparator让queue从大到小排列
然后 那边pop那边 add这边queue queue超过k个就pop 一直到最后
最后从queue pop出来的就是第K大的？

lizhongminde 发表于 2017-1-7 12:13
感觉可以这样做，既然不能改动array：
如果k=1直接返回堆顶；
k=2返回max(堆顶的左右儿子)；

看晕了....k==3的时候...k = 4 的时候怎么办呢。用什么数据结构存那个第k大的堆呢

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

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

xiaojiujie 发表于 2017-1-7 23:08
对哒，简单吧

还行。。楼主运气也不错。。我10号电面 希望人品好来个简单点的。。。

用最小堆找第k大数的话就是nlogk

第一题取第k大所在level及以上的node，再sort就好了吧，复杂度和PriorityQueue一样klogk

请问LZ第二题，题目里的as sorted as possible是怎么定义的？

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

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

第一题就是Heap Sort吧。给的是Heap，然后用delete max的重复操作Heap，k次。需要写下delete max。

补充内容 (2017-10-9 04:09):
不过这样会改变array。。。