Amazon SDE New Grad OA

求问楼主，这个题k有范围限制吗？如果是k< C(N, 2) 那光是构造长度为k的result就需要O(n^2)时间复杂度了，按照n的范围感觉肯定超时？

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

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

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

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

https://leetcode.com/playground/Q3LAat9L

补充内容 (2022-08-04 05:53 +08:00):
O(nlogn+kn)=O(nlogn)

https://www.geeksforgeeks.org/k- ... two-elements-array/ 是不是有点像这个

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

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

thomas734 发表于 2022-08-10 15:36:40
求问下为什么后面的时间复杂度是O(kn), 第一层循环n个，第二层循环min(k, n)个，每次push应该是log(k)?那就O(kn logk)了？

K是常数，nk nklogk就都是O(n)，所以dominating factor是nlogn的意思

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

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

thomas734 发表于 2022-8-13 18:20
可是这道题k不是常数啊，k也是输入的一部分，而且按题意k是可能比n大的（最大是C(n, 2)，也就是O(N^2)了 ...

那就不知道了，我感觉没法优化了...或者可能要看下k和n的范围