Amazon 新鲜OA

想问一下第二题，枚举所有pair的话，时间复杂度不就是O(n^2)了吗，再使用一个heap，这能过吗

匿名用户 发表于 2022-8-12 12:53
想问一下第二题，枚举所有pair的话，时间复杂度不就是O(n^2)了吗，再使用一个heap，这能过吗

不需要枚举所有pair，按蠡口官解heap做法就是 O(NlogN)的做法

请问lz, 719这道题的官解不都是二分吗? lz用heap做的话是先给数组排序 然后逐步改变pair之间的step, 加到满足k个这种思路吗? 谢谢

匿名用户 发表于 2022-8-13 00:26
请问lz, 719这道题的官解不都是二分吗? lz用heap做的话是先给数组排序 然后逐步改变pair之间的step, 加到满 ...

对的 就是官解第一个超时的heap方法就可以

匿名用户 发表于 2022-8-11 12:13
OA那题就是用的这个方法 没毛病

谢谢您！给您加米

第二题是不是可以quick select

hhh，我也遇到了

求问楼主什么时候投的简历（已加米）

匿名用户 发表于 2022-8-13 12:10
第二题是不是可以quick select

不行吧，他要前k个全部输出