Google店面

问：给一个N个整数的数组，

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

答：用数组，。。。
问：复杂度？
答：。。。
问：这道题还有更好的解法吗？
答：不知道
然后对方就good luck

第一次面狗家，虽然国人大哥人很好，楼主还是很紧张，水平不行，发挥也不好，求包子求安慰。。。

这个在google 面试里算是放水了吧

之前的面经题里面都是几何题，脑筋急转弯，看着就晕

Quick select o(n)

zebabc 发表于 2020-11-27 15:04
最大堆咋实现的？

维持大小为k的最大堆。对于新的元素，小于堆顶就进堆，否则就丢。

沙场小兵 发表于 2020-11-27 08:35
Quick select o(n)

后来才知道。太菜了 :(

应该用最小堆处理吧。构建堆O(nlog(n))，找前k个数是O(k)

求最小k用最大堆。求最大k用最小堆。最快的是快排O(N)。堆用数组可以实现。地里面经对于这道题提了铽别特别多

xiana406 发表于 2020-11-27 11:11
求最小k用最大堆。求最大k用最小堆。最快的是快排O(N)。堆用数组可以实现。地里面经对于这道题提了铽别特别 ...

最大堆和最小堆都是可以吧。最小堆的话，先建好，然后pop k次。跟最大堆的时间复杂度优劣，取决于k和n的大小。当然空间复杂度是差了一些。

xiana406 发表于 2020-11-27 11:11
求最小k用最大堆。求最大k用最小堆。最快的是快排O(N)。堆用数组可以实现。地里面经对于这道题提了铽别特别 ...

可以解释一下最大堆如何求最小的k个数吗

yiliaobailiao 发表于 2020-11-27 11:37
最大堆和最小堆都是可以吧。最小堆的话，先建好，然后pop k次。跟最大堆的时间复杂度优劣，取决于k和n的 ...

最大堆咋实现的？

xiana406 发表于 2020-11-27 11:11
求最小k用最大堆。求最大k用最小堆。最快的是快排O(N)。堆用数组可以实现。地里面经对于这道题提了铽别特别 ...

快排是O(nlogn)还是O(n)?