亚麻 2023 ng OA

回馈地理，贡献下dp早上做的oa1，刚收到oa2
都是地理的原题
第一题是push_head pop_head的链表题（注意，用python的同学initili

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

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

只过了一半的case）
另外oa2怎么准备啊，是一些debug的选择题和bq吗？
求加米，谢谢！

首先sort array哈, let sorted array=num
然后 我们令 left =0, right=num[size-1]-num[0]
然后我们二分出一个mid
然后我们想知道 数组中 有多少个pair, 他们的绝对差是大于mid的.
我们可以 循环 数组 i =0 , i->size-1, i++
然后 我们find 两个position,
第一个是 upper_bound(a, a+i-1, num[i]-mid)
第一个是 upper_bound(a+i, a.end, num[i]+mid)
这两个意思就是 看数组中 第i个值, 比它大mid, 小mid 一共有多少个数. 我们累加这个数 至 sum
累加完sum后, 我们看sum是否大于k, 如果大于k说明mid太大, 那就mid=right, 反之则mid=left+1
然后上面这个过程是 O(nlgn)哈.
循环完 我们就可以知道 答案中 最后一个数 应该是 left了
然后 我们现在用一个二重循环 外层 i=0, i->size-1 , 里层用二分查找 定位 左右两个端点, (就是num[i]-left, num[i]+left) 这个很快就定位到了.
然后把这段范围内的差全部加 到 res 数组中. 最后res数组中返回前k个数, (res数组长度可能会微微大于k)
如果感觉对你有帮助, 求加米~~~

匿名用户 发表于 2022-8-13 12:40
首先sort array哈, let sorted array=num
然后 我们令 left =0, right=num-num[0]
然后我们二分出一个mid ...

嗯嗯，那就是利口719的最优解的解法了，难度估计上hard了

楼主说的暴力解法就是lc上的第一个解法吗？

匿名用户 发表于 2022-8-13 12:40
首先sort array哈, let sorted array=num
然后 我们令 left =0, right=num-num[0]
然后我们二分出一个mid ...

看别人帖子 lc官方solution第一个TLE的答案就能过这道题

匿名用户 发表于 2022-8-13 13:40
首先sort array哈, let sorted array=num
然后 我们令 left =0, right=num-num[0]
然后我们二分出一个mid ...

大佬的 binary search 好强呀！
想问个问题，这个解法应该是 O(NlogN + NlogW) 吧（W 是 max num - min num）？
我写的不用 binary serach 的方法，最优复杂度是 O(NlogN + KlogN)，然后 OA 里这个题的 W 是 range 到 10^8，N 是 10^5，K 是 min(N*(N-1) / 2, 2*10^5)，所以 K 不一定是 O(N^2)，那哪个方案时间复杂度会比较低呀

匿名用户 发表于 2022-8-24 19:02
大佬的 binary search 好强呀！
想问个问题，这个解法应该是 O(NlogN + NlogW) 吧（W 是 max num - min  ...

不是大佬哈
感谢回复~
你说的对. 确实是O(NlogN + NlogW)
想知道你的KlogN的算法是什么样呢?

匿名用户 发表于 2022-8-25 16:20
不是大佬哈
感谢回复~
你说的对. 确实是O(NlogN + NlogW)

按照利口漆依酒的第一种解法写的，先排序 O(NlogN)，然后定义一个 min heap，把所有相邻的也就是 {i, i+1} 的差值放进 heap。
然后每次取出 {i, x} 的时候将 {i, x+1} 放入 heap，取 K 次，heap 最大 size 是 N-1，所以总共是 O(NlogN + KlogN)

匿名用户 发表于 2022-8-25 13:31
按照利口漆依酒的第一种解法写的，先排序 O(NlogN)，然后定义一个 min heap，把所有相邻的也就是 {i, i+1 ...

我觉得可以! 我觉得这个方法比我的还要好~

大佬可以分享一下第一题的题目吗？谢谢！