亚麻ng oa貌似新题

刚刚做完亚麻oa貌似有一题新题
第一题find min health高频

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

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

取最大值，worst case时间复杂度是O(n^2)，优化的话可以弄一个hashmap记录因数关系

楼主能分享一下用hashmap如何优化吗？我能想到用hashset的办法但还是O(n^2)

第二题求思路

Echo酱酱酱 发表于 2022-8-7 00:26
楼主能分享一下用hashmap如何优化吗？我能想到用hashset的办法但还是O(n^2)

假如当前元素找到因数的话记录因数的index，没有的话记录为-1，我又想了想好像对worst case没有帮助。。

匿名用户 发表于 2022-8-7 09:13
假如当前元素找到因数的话记录因数的index，没有的话记录为-1，我又想了想好像对worst case没有帮助。。

这样应该还是nested loop

楼主还记得第二题的数据范围吗？n^2应该会超时吧？

请问楼主第二题的具体步骤是什么？

求问楼主timeline

匿名用户 发表于 2022-8-7 20:13
楼主还记得第二题的数据范围吗？n^2应该会超时吧？

应该是10^5 的确有几个test是TLE了 但是也没想到啥其他的方法

积分不够，看不完整第二题，请问数组里元素的范围有吗？如果有的话，比如是10^5以内，因为每个数的因子最多sqrt(1e5)个，那么可以O(n * sqrt(1e5))处理出每个元素的所有因子，存到vector<vector<>> fac里，第一个vector的下标是因子，里面的vector存有这个因子的元素下标，因为是按顺序处理的，所以这个vector里下标也是有序的，之后遍历数组，fac[num[i]]最后两个下标，check是否满足条件。整体时间和空间复杂度都是O(n * sqrt(1e5))。如果数都是int范围内的，暂时还不知道咋做。

求米~