Google店面

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

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

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

答：用数组，。。。
问：复杂度？
答：。。。
问：这道题还有更好的解法吗？
答：不知道
然后对方就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)。堆用数组可以实现。地里面经对于这道题提了铽别特别多

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

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

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)?