脸电面

攒人品，发面经。

小哥迟到了五分钟，上来寒暄了两分钟就直接做题，最后还留了五分钟问问题。

第一题，应该是利口的找第一个错误版本那题。

第二题，找第k个最大元素。试探性的问了一下小哥，有时间跟空间要求没有，他说空间不超过k，所以第一个解是用的小根堆。
跟进一，问时间还能不能优化，我说可以，但是要改变数组结构或者复制一份，给了递归的快

游客，本帖隐藏的内容需要积分高于 188 才可浏览，您当前积分为 0。
查看如何攒积分 Click here for more info.

销好，第一反应是没了，还没来得及思考，面试官说要我不要想了，问问题吧。是不是面试官发现自己也弄错了。

engx2 发表于 2019/06/25 06:36:32
在最大值和最小值之间二分，复杂度nlogk

准确说是
nlog max - min


补充内容 (2019-7-24 06:23):
@HOMIE 反对完给个建议啊 什么地方说错了？

谢谢楼主分享！

快选需要递归吗？空间O1吧 不过需要inplace改变输入数组

第四问 binary search？

nlogn 每次数一数比目标少的数字数目？

在最大值和最小值之间二分，复杂度nlogk

跟进二 什么叫写成顺序的呢？

用PriorityQueue是log(n)

用heap时间是nlogk，空间可以搞成k
用quick sort时间是n，空间是1

"跟进一，问时间还能不能优化，我说可以，但是要改变数组结构或者复制一份，给了递归的快选。"

第一个follow up，如果每个元素都是>=0的Integer, 是不是也可以用Bucket Sort啊？用额外空间，创建bucket，然后扫描bucket，得到第K大的元素