亚麻OA 5/5

贡献一个data point，都是地里最近的

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

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

第二题机器人转圈圈

求问楼主 第一题 有好的解法吗  用离扣 似吴似 的解法能过所有testcase嘛

notfrom1m3fd 发表于 2021-05-07 15:23:12
求问楼主 第一题 有好的解法吗  用离扣 似吴似 的解法能过所有testcase嘛

我是参考地理有人总结的答案的。分成两组 分别找到和小于总价的pair 然后iterate group1 对group2 进行二分。可以通过所有test case

tracyyjyyjyyjy 发表于 2021-5-9 13:03
我是参考地理有人总结的答案的。分成两组 分别找到和小于总价的pair 然后iterate gro ...

谢谢分享  哈哈 不过我没碰到这题。

第一题如果用二分的话，时间复杂度会变成O(n^2*logn^2), n 为 input array 的长度。 可以考虑根据 dollars 构建一个 长度为 dollars 的 prefixSum array。这样子后面一半查询时间就是O(1), 总时间是 O(n^2) . 由于 数组长度是 10^3, dollar 大小是 10^9. 所以实际的 空间复杂度是一样的。  

楼主能发下在地里看到的OA信息嘛？我没找到，题目看的一脸懵。。