狗家面筋 -谷歌

找中位数是用partition吗，那是不是不一定要找median，找到第k大的也可以继续这么操作呢？

感觉不对吧，为啥只能是list里面的数，有这个要求吗？
比如输入[20, 50], bound 是30，threshold 15才是最佳的

看见鼓励招女程序员的项目我有点激动 但反应过来我不是程序员。。。我一定是最近担心实习太紧张了

elizabethxiazhi 发表于 2017-1-14 12:03
对的。。。

这不就是二分搜索么，什么叫你居然用二分搜索。而且以你的表达，肯定好多人看不懂第二题的意思

muyunhai 发表于 2017-1-15 08:01
感觉根据楼主的描述，答案只能是list里的数。中位数就是log的中位数，需要这么做因为我认为input无序，排 ...

感觉你和楼主互相理解对方，你的方法是quickselect？

clydexu 发表于 2017-1-17 05:16
感觉你和楼主互相理解对方，你的方法是quickselect？

是的 先用quickselect
binary search的前提是sorted， 所以时间是O(NlogN）

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

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

mashiro_sky 发表于 2017-1-17 06:04
哈哈你一说quickselect我就懂了。。。那解题思路就是这样咯：
1. 找一个pivot，不一定是什么中位数。。 ...

我也是这么理解的，一开始看到中位数就有点晕！其实找一个pivot就可以apply这个算法！这题还是挺有趣的感觉....

mashiro_sky 发表于 2017-1-17 06:04
哈哈你一说quickselect我就懂了。。。那解题思路就是这样咯：
1. 找一个pivot，不一定是什么中位数。。 ...

照你这么说，我直接把pivot选成最小的数，不是一下就出来了

laiguojiuhao 发表于 2017-1-17 06:20
照你这么说，我直接把pivot选成最小的数，不是一下就出来了

设成最小的也出不来啊，那样总和肯定小于capacity，就还要继续找 capacity-pivot 的bound...