Airbnb Skype 两轮

匿名用户-3ZXHQ *2022-2-19 06:44:48* · 2022-2-19 06:44:48

这题感觉可以用quickselect找k大元素，然后奇数偶数k的情况不同。

chipmunks123

本帖最后由 chipmunks123 于 2022-2-20 23:22 编辑

上面讨论的binary search的解法是可行的。但是有个问题就是这个所谓的large file的定义是什么呢？能放进内存中吗

AaronZhao

lower bound 和higher bound不能是int最大最小值，这样会可能出现类似quick select的worst case就是变成了O n*2的时间复杂度，只需要取这组数之中的最大最小值作为bound就可以了，不然还不如直接Arrays.sort()来的快