亚麻 oa1 ng 2023

两道题都是最近出现过的老题。第二题的图片贴上

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

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

19

求加米求加米！

微信用户_pshzc 发表于 2022-8-16 00:09
第二题就是两个数两两比较一下吗，还有更优解嘛？

用heap。lc719 solution有详细解释

第二题就是两个数两两比较一下吗，还有更优解嘛？

微信用户_pshzc 发表于 2022-8-15 23:09
第二题就是两个数两两比较一下吗，还有更优解嘛？

感觉没了。因为前k的都要，不能用binary search优化了

匿名用户 发表于 2022-8-16 20:23
感觉没了。因为前k的都要，不能用binary search优化了

这个和719有什么变种吗？ 怎么看来看去都是一样的内容。求指导一下。

微信用户_777a65f 发表于 2022-8-19 16:26
这个和719有什么变种吗？ 怎么看来看去都是一样的内容。求指导一下。

这个要返回前k个，719只要返回第k个就好

匿名用户 发表于 2022-8-19 19:13
这个要返回前k个，719只要返回第k个就好

懂了懂了，没注意到这么细节。。

匿名用户 发表于 2022-8-16 23:23
感觉没了。因为前k的都要，不能用binary search优化了

利口第一种解法是O(NlogN + KlogN)，K = O(N^2) 的话就是 O(N^2 logN) 了
https://www.1point3acres.com/bbs/thread-919328-1-1.html 这里有位回帖提供了使用 binary search 的优化方案，是 O(NlogN + NlogW) 的，参照利口第三种解法，W 是数据范围
不过 OA 里这个题的 W 是 range 到 10^8，N 是 10^5，K 是 min(N*(N-1) / 2, 2*10^5)，K 不一定是 O(N^2)，所以还真不知道哪个比较好……