Amazon SDE New Grad OA

倒序浏览 · 2022-8-2 11:15:13

2nd pr

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

Zergeometer

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

来自APP · 2022-8-2 11:16:35

之前没刷过这题，有人有思路吗

xahbal1

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

xu112358

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

Zhuohong

xu112358 发表于 2022-8-2 17:24
sort(skill), int[] diff = new int[skill.length-1]
diff=skill-skill. 再sort diff 或者maxheap 拿前K小 ...

我觉得直接sliding window就好了啊

Zhuohong

一遍sliding window maximum，一遍sliding window minimum，max-min = variance

来自APP · 2022-8-2 23:31:47

Zhuohong 发表于 2022-08-02 04:35:02
一遍sliding window maximum，一遍sliding window minimum，max-min = variance

同学能详细解释一下吗

lihe14569

这个k的contains是什么呢？ k < n 还是k < C(N, 2)

Artemicy_D

lihe14569 发表于 2022-08-02 12:43:46
这个k的contains是什么呢？ k < n 还是k < C(N, 2)

应该是后者，k可以大于N的

来自APP · 2022-8-3 03:51:03

xu112358 发表于 2022-08-02 02:24:12
sort(skill), int diff = new int
diff=skill-skill. 再sort diff 或者maxheap 拿前K小的element

diff不一定是相邻两个数，可能是任意两个数的，那样的话时间就不够了吧